# How to solve non-homogeneous recurrence relations?

I have been looking around for a general method to solve non-homogeneous recurrence relations.

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.

-

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.

-

Try putting $an+b+cn2^{n}$ into the equation where $a,b,c$ are some constants to be determined and see if the recurrence holds.

-
Into what equation? The whole $f(n) = f(n-1) + 2f(n-2) + n + 2^n + K$? –  Zol Tun Kul Apr 10 '14 at 3:49
yes just plug it in and see what you get. –  lance wellton Apr 10 '14 at 3:53
I'd have $$f(n) = f(n-1) + 2f(n-2) + n + 2^n + K + an + b + cn2^n$$ and still wouldn't have the fainted idea what's going on. –  Zol Tun Kul Apr 10 '14 at 3:56
what I mean is try $f(n)=an+b +cn2^{n}$. –  lance wellton Apr 10 '14 at 5:56

I will use lance wellton's method and finish the problem. It is based on the very simple undetermined method for linear non-homogeneous differential equations, which you can find in any elementary ODE book. As lance wellton suggests, just try $f(n)=an+b+cn2^n$. Then $$f(n)-f(n−1)-2f(n−2)=-2an+(5a-2b)+3c\,2^n/2.\qquad (1)$$ We want the RHS of (1) to be equal to $n+2^n+K$, hence we set $c=2/3$, $a=-1/2$, $b=-K/2-5/4$ and the general solution reads: $$f(n)= b_1\,2^n+b_2\,(−1)^n-n/2-K/2-5/2+2n2^n/3.$$ Then use $b_1$ and $b_2$ to get you boundary conditions.

-