Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
    
Into what equation? The whole $f(n) = f(n-1) + 2f(n-2) + n + 2^n + K$? –  Zol Tun Kul Apr 10 at 3:49
    
yes just plug it in and see what you get. –  lance wellton Apr 10 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 at 3:56
    
what I mean is try $f(n)=an+b +cn2^{n}$. –  lance wellton Apr 10 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.