I am trying to solve the non-homogeneous linear recurrence relation:
$$f(n) = 6f(n-1) – 5,\quad f(0) = 2.$$
How do I go about doing it? This is so different from solving a homogeneous recurrence relation.
[Math] non homogeneous recurrence relation
recurrence-relations
Related Solutions
You can use generating functions, as we did in the single variable case.
Let $G(x,y)=\sum_{m,n\ge 0}F(n,m) x^n y^m$. We'll express $G$ in a nice form from which one can recover $F(n,m)$.
As you didn't specify initial conditions, let $$H_1(x)=\sum_{n\ge0} F(n,0)x^n, H_2(y)=\sum_{m\ge0} F(0,m)y^m, c=F(0,0)$$
By the recurrence of $G$, if we multiply it by $1-x-y$, most of the terms will cancel. I'll elaborate on that.
I choose $1-x-y$ in a similar manner to that of constructing the characteristic polynomial in one variable: $1$ corresponds to $F(n,m)$, $x$ to $F(n-1,m)$ and $y$ to $F(n,m-1)$, i.e. $F(n-a,m-b)$ is replaced by $x^ay^b$.
$$G(x,y)(1-x-y)=\sum_{m,n\ge 0}F(n,m) (x^n y^m-x^{n+1}y^m-x^{n}y^{m+1})=$$ We'll group coefficients of the same monomial: $$\sum_{m,n \ge 1} (F(n,m)-F(n-1,m)-F(n,m-1)) x^{n}y^{m}+$$ $$\sum_{n \ge 1} (F(n,0)-F(n-1,0)) x^{n}+\sum_{m \ge 1} (F(0,m)-F(0,m-1)) y^{m}+F(0,0)=$$ $$H_1(x)(1-x) + H_2(y)(1-y)-c$$
So, finally, $$G(x,y) = \frac{H_1(x)(1-x) + H_2(y)(1-y)-c}{1-x-y}$$ (Compare this to the relation $Fib(x)=\frac{x}{1-x-x^2}$ where $Fib$ is the generating function of the Fibonacci sequence.)
How do we recover $F$? We use the formal identity $\frac{1}{1-x-y}=\sum_{i\ge 0}(x+y)^i$. Let $S(x,y)=H_1(x)(1-x) + H_2(y)(1-y)-c=\sum_{n,m} s_{n,m} x^ny^m$. It gives us: $$G(x,y) = \sum_{i \ge 0}S(x,y)(x+y)^i = \sum_{n,m \ge 0} (\sum_{a,b \ge 0}s_{a,b} \binom{n+m-a-b}{n-a})x^ny^m$$ So $F(n,m) = \sum_{a,b \ge 0}s_{a,b} \binom{n+m-a-b}{n-a}$. I have an hidden assumption - that $S$ is a polynomial! Otherwise convergence becomes an issue.
I guess that your initial conditions are $F(n,0)=1, F(0,m) = \delta_{m,0}$, which give $S(x,y)=1$, so $F(n,m)=\binom{n+m}{n}$.
EDIT: In the general case, where $F(n,m)=\sum_{a,b} c_{a,b}F(n-a,m-b)$ where the sum is over finitely many tuples in $\mathbb{N}^{2} -\setminus \{ (0,0) \}$, the generating function will be of the form $\frac{H(x,y)}{1-\sum_{a,b} c_{a,b}x^a y^b}$ where $H$ depends on the initial conditions.
When we had one variable, we wrote $\frac{q(x)}{1-\sum a_i x^i} =\sum \frac{q_i(x)}{1-r_i x}$ where $r_i^{-1}$ is a root of $1-\sum a_i x^i$ and used $\frac{1}{1-cx} = \sum c^ix^i$.
With 2 variables, this is not always possible, but we can write $\frac{1}{1-\sum_{a,b} c_{a,b}x^a y^b}=\sum_{i \ge 0} (\sum_{a,b} c_{a,b}x^a y^b)^{i}$ and use the binomial theorem to expand. We can also use complex analysis methods to derive asymptotics of $F(n,m)$ from the generating functions.
Just use generating functions. Define $F(z) = \sum_{n \ge 0} f(n + 1) z^n$, write your recurrence as: $$ f(n + 2) = f(n + 1) + 2 f(n) + n + 2 + 4 \cdot 2^n + K $$ Multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums: $$ \frac{F(z) - f(1) - f(2) z}{z^2} = \frac{F(z) - f(1)}{z} + 2 F(z) + \frac{z}{(1 - z)^2} + \frac{4}{1 - 2 z} + \frac{K + 2}{1 - z} $$ This because: \begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} Solving for $F(z)$, as partial fractions: $$ F(z) = \frac{6 K + 13}{12(1 + z)} + \frac{3 K - 1}{1 - 2 z} - \frac{2 K + 5}{4 (1 - z)} + \frac{2}{3 (1 - 2 z)^2} - \frac{1}{6 (1 + z)^2} $$ Using the generalized binomial theorem you have: $$ \binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1} $$ In particular: $$ \binom{-2}{k} = (-1)^k (k + 1) $$ This allows to read off the coefficients from the above.
Best Answer
This answer shows one elementary method of solving exactly this kind of problem. There are many others, most of them considerably more general; this link gives an brief introduction to some of them. This PDF goes into considerably more detail.