I have been looking around for a general method to solve non-homogeneous recurrence relations.
-
Solving non homogeneous recurrence relation seems to be having almost the same problem as me. There is one answer that I absolutely don't understand.
-
Establishing formula from recurrence. Brian's answer explains that his method is better suited for relations of the form $f(n)=af(n−1)$. What if my relation is not of that form?
Can you explain to me how to solve non-homogeneous recurrence relations?
For instance, this
$$f(1) = f(2) = K$$
$$f(n) = f(n-1) + 2f(n-2) + n + 2^n + K$$
I only know part of the process:
First, we take care of the homogeneous part:
$$f(n) – f(n-1) – 2f(n-2)$$
The characteristic equation is:
$$a^2-a-2$$
Which factors to:
$$(a – 2)(a + 1)$$
Therefore, the homogeneous formula is of the form:
$$f_H(n) = b_1(2)^n+b_2(-1)^n$$
And this is as much as I know about non-homogeneous recurrence relations. How do I proceed? I've seen several documents, but somehow, they all seem to describe different concepts that just end up confusing me more.
Best Answer
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.