Help solving a non-homogeneous recurrence relation

Question

I have this recurrence relation: $$a_{n+1} + 2a_{n}+2a_{n-1} = ( n+3)\times2^n,$$ where $a_0= -\frac{2} {5} $, and $a_1=\frac{46}{5}$

So for the homogeneous part, I have $x^2+2x+2=0$ or $x=1$.

But I don't know what to do with the non-homogeneous part.

Any help would be appreciated. Thank you in advance.

Answer 1

Hint:   divide by $2^n$ and write it as:

$$ 2 \cdot \frac{a_{n+1}}{2^{n+1}} + 2 \cdot \frac{a_{n}}{2^n}+\frac{a_{n-1}}{2^{n-1}} = n+3 $$

Then solve $\,2b_{n+1}+2b_n+b_{n-1}=n+3\,$.

Answer 2

You need to guess a particular solution to the inhomogeneous equation. Try $$a_n=(an+b)2^n$$ for undetermined coefficient $a$ and $b$. Solve for $a$ and $b$. Then the following is true: the general solution to the inhomogeneous equation is the general solution to the homogeneous equation, PLUS any particular solution to the inhomogeneous equation.

So, you find the general solution to the homogeneous equation as you ordinarily would. Then you add the particular solution you got by solving for $a$ and $b$ above. Finally you substitute the initial conditions to get rid of the undetermined coefficients in the general solution.

I hope that's comprehensible. Don't hesitate to ask questions.

Answer 3

Just like for non-homogeneous linear differential equations:

You have to find one particular solution of the non-homogeneous recurrence relation, and add the general solution of the homogeneous recurrence.

The r.h.s. is standard: a linear polynomial in $n$ times $2^n$. As $2^n$ is not a solution of the hommogeneous recurrence, a particular solution will have the same form, i.e. try $$a_n=(cn+d)2^n$$ Plugging it in the l.h.s., you'll obtain by identification with the r.h.s. a linear system in $c$ and $d$.

Answer 4

Use generating functions. Write your recurrence without subtractions in indices: $$ a_{n + 2} + 2 a_{n + 1} + 2 a_n = (n + 4) \cdot 2^{n + 1} $$ Define: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ Multiply the recurrence by $z^n$, sum over $n \ge 0$: $$ \sum_{n \ge 0} a_{n + 2} z^n + 2 \sum_{n \ge 0} a_{n + 1} z^n + \sum_{n \ge 0} a_n z^n = 2 \sum_{n \ge 0} n \cdot 2^n z^n + 8 \sum_{n \ge 0} 2^n z^n $$ Recognize some sums: $$ \frac{A(z) - a_0 - a_1 z}{z^2} + 2 \frac{A(z) - a_0}{z} + 2 A(z) = 4 \frac{z}{(1 - 2 z)^2} + 8 \frac{1}{1 - 2 z} $$ Here we used: $$ z \frac{d}{d z} \sum_{n \ge 0} u_n z^n = \sum_{n \ge 0} n u_n z^n $$ which gives: $$ \sum_{n \ge 0} n \cdot 2^n z^n = z \frac{d}{d z} \frac{1}{1 - 2 z} = \frac{2 z}{(1 - 2 z)^2} $$ This gives, as partial fractions: $$ A(z) = \frac{2 (54 z^3 - 68 z^2 + 25 z - 1)}{5 (1 - 2 z)^2 (1 + 2 z + 2 z^2)} = \frac{1}{5} \cdot \frac{1}{(1 - 2 z)^2} + \frac{9}{25} \cdot \frac{1}{1 - 2 z} + \frac{24 - 144 z}{1 + 2 z + 2 z^2} $$ The first terms are easy: $$ \frac{1}{1 - 2 z} = \sum_{n \ge 0} 2^n z^n \\ \frac{1}{(1 - 2 z)^2} = \sum_{n \ge 0} \binom{-2}{n} 2^n z^n = \sum_{n \ge 0} \binom{n + 2 - 1}{2 - 1} 2^n z^n = \sum_{n \ge 0} (n + 1) \cdot 2^n z^n $$ For the last one we need complex numbers: $$ \frac{24 - 144 z}{1 + 2 z + 2 z^2} = \frac{12 + 84 i}{1 + (1 - i)z} + \frac{12 - 84 i}{1 + (1 + i) z} $$ The last terms are troublesome. We can write: $$ 12 \pm 84 i = 60 \sqrt{2} \exp(\pm i \arctan(7)) \\ 1 \pm i = \sqrt{2} \exp(\pm i \arctan(1)) = \sqrt{2} \exp\left(\pm \frac{\pi i}{4}\right) $$ So we have for the coefficient of $z^n$: $\begin{align*} [z^n] \frac{24 - 144 z}{1 + 2 z + 2 z^2} &= 60 \sqrt{2} \exp(i \arctan(7)) \cdot (\sqrt{2})^n \exp\left(\frac{n \pi i}{4}\right) + 60 \sqrt{2} \exp(- i \arctan(7)) \cdot (\sqrt{2})^n \exp\left(-\frac{n \pi i}{4}\right) \\ &= 2 \cdot 60 \sqrt{2} \cos(\arctan(7)) \cdot (\sqrt{2})^n \cos\left(\frac{n \pi}{4} \right) \\ &= \frac{120 \sqrt{2}}{5 \sqrt{2}} \cdot (\sqrt{2})^n \cos\left(\frac{n \pi}{4} \right) \\ &= 24 \cdot (\sqrt{2})^n \cos\left(\frac{n \pi}{4} \right) \end{align*}$ This introduces oscilating terms.