5

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?

Saturn
  • 7,191
  • 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? – Saturn 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
  • 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. – Saturn Apr 10 '14 at 13:10

5 Answers5

8

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

picakhu
  • 4,906
Yiyuan Lee
  • 14,435
  • 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)$? – Saturn 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. – Yiyuan Lee Apr 10 '14 at 12:48
2

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

user88595
  • 4,549
1

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.

David
  • 82,662
  • 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
  • In that case I would go straight for $an^22^n$ as the lower terms are covered by arbitrary constants so there's no need to find them. I'll notice that it this special case it doesn't work (I get $a=0$) and try $(an^3 + bn^2)2^n$ which gives an answer. – user88595 Apr 10 '14 at 13:17
  • Not sure if I have understood you correctly, but if you have to actually figure out the coefficients before you realise that it doesn't work, then that sounds to me like a rather clumsy method. My method works fine in this case - try it. – David Apr 10 '14 at 13:21
  • If, hypothetically, there was yet another shared term between my guess and the $f(n)$, I would have to multiply the guess by $n$ again, right? In that case the guess would be $(an^3+bn^2)2^n$? – Saturn Apr 10 '14 at 13:22
  • @Omega, that's right. This could happen with a second order recurrence having $(An+B)2^n$ in the homogeneous solution and $n2^n$ on the RHS. I would go (1) $an2^n$; (2) $(an+b)2^n$ - doesn't work; (3) $(an^2+bn)2^n$ - still doesn't work; (3 again) $(an^3+bn^2)2^n$ and this will work. – David Apr 10 '14 at 13:22
  • I'm trying to apply this with another exercise at the moment. "If necessary modify this by including "lower order" terms" - what determines whether it is necessary or not to include lower order terms? – Saturn Apr 10 '14 at 13:34
  • You always add lower order terms if there are any. The "if necessary" was intended to exclude cases like $RHS=2^n$ in which there aren't any lower order terms. Sorry, maybe I didn't write that very clearly. – David Apr 10 '14 at 13:41
  • I'm working on one where the homogeneous solution is $(b_0+b_0n)\cdot(-3)^n$ and $RHS = 4 + 3^n$. In this case, I don't need to add a lower order term right? – Saturn Apr 10 '14 at 13:46
  • That's right. And you don't need step 3 either, because a constant times $3^n$ is not the same as a constant times $(-3)^n$. – David Apr 10 '14 at 13:47
  • In step 1, "try something like RHS", can you elaborate on that? In this example, where $RHS = n2^n$, you decided to use $an2^n$. I do see that your decision is "like the RHS", but what made you specifically choose this and not something else? Or is it just a matter of copy-pasting the RHS? Basically, if I had $RHS = 4+3^n$, would it be $a4+a3^n$? – Saturn Apr 10 '14 at 13:54
  • Use the RHS, but modified so that each term is multiplied by an unknown constant. So if $RHS=2+3\times4^n$ you would start with $a+b\times4^n$. – David Apr 10 '14 at 14:15
  • If I multiply each term by an unknown constant, wouldn't it be $2a+3b\times4^n$ instead? – Saturn Apr 10 '14 at 15:31
  • Ok, doing what you said, for an $RHS = 4+3^n$ it would be $a+b\cdot 3^n$? – Saturn Apr 10 '14 at 15:39
  • Both of your last two suggestions are fine, because you have yet to evaluate the constants. It doesn't matter if your solution comes out as, for example, $14+15\times4^n$ or $2\times7+3\times5\times4^n$, – David Apr 10 '14 at 20:41
0

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

ajotatxe
  • 65,084
0

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

vonbrand
  • 27,812