3

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.

I have found from the characteristic polynomial the general homogenous solution is: $a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.

For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks

user1176409
  • 1
yhu
  • 191
  • Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct. – abiessu Oct 22 '13 at 18:20
  • It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution? – yhu Oct 22 '13 at 18:32
  • One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself? – abiessu Oct 22 '13 at 18:48
  • Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it? – yhu Oct 22 '13 at 18:54
  • See https://math.stackexchange.com/questions/261964/a-way-to-solve-this-relation-a-n-4a-n-1-4a-n-22n?noredirect=1&lq=1 and https://math.stackexchange.com/questions/1957951/solve-a-n-4a-n-1-4a-n-2-2n – user236182 Sep 28 '17 at 13:04

2 Answers2

4

Don’t try to find a separate particular solution; just try the general solution

$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n\;.\tag{1}$$

You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.

Brian M. Scott
  • 616,228
  • I have tried this and I believe the OP has as well, perhaps you could give a stronger hint? – abiessu Oct 23 '13 at 00:38
  • @abiessu: It’s a complete set of directions as it stands. Where did you run into trouble? – Brian M. Scott Oct 23 '13 at 00:40
  • I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$... – abiessu Oct 23 '13 at 00:45
  • @abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values. – Brian M. Scott Oct 23 '13 at 00:46
  • I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it. – abiessu Oct 23 '13 at 01:47
  • @abiessu: I thought that it was probably what you had in mind in your comment to the OP. Did you get the right constants? If I remember correctly, they’re $1,-\frac18$, and $\frac18$. – Brian M. Scott Oct 23 '13 at 01:50
  • I had gotten $c_1=1, c_2=-c_3$ but I had forgotten to allow non-integer constants... – abiessu Oct 23 '13 at 03:00
  • Just one note. Denote $$a_n = 2^{n-2}b_n, ~~~ n\in \mathbb{Z}+.$$ Then $$b{n+2}-2b_{n+1}+b_n = 1 = const ~~~ (!!!)$$ It is related to finite difference of $2$nd order. This difference is constant. That's why $b_n$ pattern/formula is the polynomial of $2$nd order (not $3$rd, not $1$st, ...). – Oleg567 Oct 23 '13 at 10:14
  • Okay thank you for your help, I have never seen a solution quite like that, but it works! Will see if I can use it on some of my others now. – yhu Oct 23 '13 at 16:13
  • @Kumar2: You’re welcome. – Brian M. Scott Oct 23 '13 at 16:16
1

Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n \ge 0$. Recognize e.g. \begin{align} \sum_{n \ge 0} a_{n + k} z^k &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k - 1}}{z^k} \\ \sum_{n \ge 0} 2^n z^n &= \frac{1}{1 - 2 z} \end{align} to get $$ \frac{A(z) - 1 - 2 z}{z^2} - 4 \frac{A(z) - 1}{z} + 4 A(z) = \frac{1}{1 - 2 z} $$ As partial fractions: $$ A(z) = \frac{1}{4} (1 - 2 z)^{-3} - \frac{1}{2} (1 - 2 z)^{-2} + \frac{5}{4} (1 - 2 z)^{-1} $$ Using the generalized binomial theorem you can read off the coefficients: \begin{align} a_n &= \frac{1}{4} \binom{-3}{n} (-2)^n - \frac{1}{2} \binom{-2}{n} (-2)^n + \frac{5}{4} \binom{-1}{n} (-2)^n \\ &= \frac{1}{4} \binom{n + 3 - 1}{3 - 1} 2^n - \frac{1}{2} \binom{n + 2 - 1}{2 - 1} 2^n + \frac{5}{4} \binom{n + 1 - 1}{1 - 1} 2^n \\ &= \frac{1}{4} \left( \frac{(n + 2) (n + 1)}{2} - 2 \frac{n + 1}{1} + 5 \right) \cdot 2^n \\ &= (n^2 - n + 8) \cdot 2^{n - 3} \end{align}

vonbrand
  • 27,812