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.

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?

share|improve this question
    
I think that $f_H(n)=b_02^n$. –  ajotatxe Apr 10 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 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 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 at 12:54
1  
@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 at 13:10

5 Answers 5

(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.

share|improve this answer
    
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 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. –  Yiyuan Lee Apr 10 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$.

share|improve this answer
    
Typo: you have $c_1$ twice in your suggested guess. –  rajb245 Apr 10 at 12:50
    
@rajb245 : cheers –  user88595 Apr 10 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 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.

share|improve this answer
    
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 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 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 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 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 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$.

share|improve this answer

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$.

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.