# What particular solution should I guess for this relation?

Just trying to solve a non-homogeneous recurrence relation:

$$f(n) = 2f(n-1) + n2^n$$

$$f(0) = 3$$

Characteristic equation is:

$$f(n) - 2f(n-1) = 0$$

$$a-2 = 0$$

$$a = 2$$

Homogeneous solution is:

$$f_H(n) = b_0\cdot (2)^n$$

Right-hand side is:

$$n2^n$$

What is the particular guess I should be taking based on this?

-
I think that $f_H(n)=b_02^n$. –  ajotatxe Apr 10 '14 at 12:31
@ajotatxe: This stuff confuses me. If we chose $b_0$ to replace $n$ there, why aren't we replacing the exponential $n$ too? –  Zol Tun Kul Apr 10 '14 at 12:33
What @ajotatxe is saying is that if $a=2$, the form of the homogeneous solution is $2^n$ and not $(-2)^n$ as you have written. –  rajb245 Apr 10 '14 at 12:52
@Omega : I don't get it. I corrected the sign as it is $2^n$ and you edited back to $(-2)^n$. Why? Do you think it is $-2$ and need help to clarify this? –  user88595 Apr 10 '14 at 12:54
@user88595: Oh no, actually, I saw your comment and said "yeah I should invert the sign" so I went and inverted it without realising you already had inverted so it returned to its original form lol. –  Zol Tun Kul Apr 10 '14 at 13:10

(This is not a guess, but rather an approach to finding the solution.)

Firstly, we rearrange the given relation to get:

$$f(n) - 2f(n-1) = n2^n$$

Divide throughout by $2^n$. This gives us:

$$\frac{f(n)}{2^n} - \frac{f(n-1)}{2^{n-1}} = n$$

Do a summation to exploit the potential cancellations on the LHS:

$$\sum_{i = 1}^n\left(\frac{f(i)}{2^i} - \frac{f(i-1)}{2^{i-1}}\right) = \sum_{i = 1}^n i$$ $$\frac{f(n)}{2^n} - \frac{f(0)}{2^0} = \frac{n(n+1)}{2}$$ $$\frac{f(n)}{2^n} = \frac{n(n+1)}{2} + 3$$ $$f(n) = 2^{n-1}(n^2 + n + 6)$$

In general, if you have stuffs like $a_n - ka_{n-1} = b_n$ where $k$ is a constant, dividing throughout by $k^n$ might be a good way to start.

-
How did you rearrange $f(n) = 2f(n-1) + n2^n$ to $f(n)-f(n-1) = n2^n$? I ask because of $2f(n-1)$, how did it become just $f(n-1)$? –  Zol Tun Kul Apr 10 '14 at 12:46
I did two steps in one for that one. I've split them up to make it less confusing, do have a look. –  Lee Yiyuan Apr 10 '14 at 12:48

The answer by Yiyuan Lee is very good and clever.

More generally, you will need to solve the homogeneous as you did and notice that $a = 2$. Then look at the RHS and notice that it also is $2^n$ so you need to look for a solutions of the form : $$cn2^n$$ However this is the RHS so add a $n^2$ term to try finding a solution of the form : $$(c_1n^2 + c_2n)2^n$$ Substitute this into the equation and solve for $c_1$ and $c_2$.

-
Typo: you have $c_1$ twice in your suggested guess. –  rajb245 Apr 10 '14 at 12:50
@rajb245 : cheers –  user88595 Apr 10 '14 at 12:52
Your answer directly answers the original question, and more generally shows the pattern of what to do when the forcing term already solves the homogeneous equation. Very nice answer. –  rajb245 Apr 10 '14 at 12:58

Suggestion: work it out in three steps.

1. Try something like the RHS, say $an2^n$.

2. If necessary modify this by including "lower order" terms - in this case, change the guess to $(an+b)2^n$.

3. Compare the homogeneous solution, here $f_H(n)=A2^n$. If your guess has any terms shared with $f(n)$, multiply the guess by $n$. Repeat until there are no shared terms. In this case $(an+b)2^n$ has the term $b2^n$ in common with $f_H(n)$, so modify the guess to $(an^2+bn)2^n$. There is now nothing in common with $f_H(n)$, so this is the one to go with.

-
Adding a $b$ in step 2 will not work as this is the solution to the homogeneous equation. This is the same as finding a constant which you'll add later on to the arbitrary constant. –  user88595 Apr 10 '14 at 12:39
@user88595, exactly! That is why step 3 is there. But you have to put the $b$ in there as otherwise you will end up with $an^22^n$ which will not in general give a solution. And it is not the same as adding $b$, it is adding $b2^n$ (which as I have already explained will not b in the final answer anyway). –  David Apr 10 '14 at 12:42
@user88595 notice that your final suggestion in your answer is in fact exactly the same as mine. Sorry to have to say this but I think you should read answers much more carefully before commenting. –  David Apr 10 '14 at 12:46
Ok, I guess it's just a different method. My point is that I simply add new powers of $n$ until it's enough as I know beforehand that the constant won't work avoiding eventual calculations. When I read your answer I understand step 2 is step 1 with another constant. –  user88595 Apr 10 '14 at 12:51
@user88595 how do you apply your method if it's a second order recurrence with homogeneous solution $(An+B)2^n$ and the right hand side is $n2^n$? –  David Apr 10 '14 at 12:58

I have tried to compute some values and I found this formula:

$$f(n)=3\cdot2^n+\frac{n^2+n}22^n$$

It is easy to prove it by induction on $n$.

-

Just solve the bugger by using generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, adjust indices so there aren't subtractions: $$f(n + 1) = 2 f(n) + (n + 1) 2^{n + 1}$$ Multiply by $z^n$, sum over $n \ge 0$, recognize: \begin{align} \sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) - f(0)}{z} \\ \sum_{n \ge 0} (2 z)^n &= \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} n 2^n z^{n - 1} &= \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} (n + 1) 2^{n + 1} z^n &= \frac{2}{(1 - 2 z)^2} \end{align} This gives: $$\frac{F(z) - 3}{z} = 2 F(z) + \frac{2}{(1 - 2 z)^2}$$ Solving for $F(z)$, as partial fractions: $$F(z) = \frac{3}{1 - 2 z} - \frac{1}{(1 - 2 z)^2} + \frac{1}{(1 - 2 z)^3}$$ Using the generalized binomial theorem: \begin{align} f(n) &= 3 \binom{-1}{n} (-2)^n - \binom{-2}{n} (-2)^n + \binom{-3}{n} (-2)^n \\ &= 3 \cdot 2^n - (n + 1) 2^n + \frac{(n + 2) (n + 1)}{2} 2^n \\ &= (n^2 + n + 6) \cdot 2^{n - 1} \end{align} At first glance, this checks, as $f(0) = 3$.

-