3

I need to solve the following recurrence relation: $a_{n+2} + 2a_{n+1} + a_n = 1 + n$


My solution:

Associated homogeneous recurrence relation is: $a_{n+2} + 2a_{n+1} + a_n = 0$

Characteristic equation: $r^2 + 2r + 1 = 0$

Solving the characteristic equation, we get: $r = -1$ with multiplicity $m = 2$

Therefore, solution of the homogeneous recurrence relation is: $a_n^{(h)} = (c_1 + c_2n)(-1)^n$

Let the particular solution of the given equation be

$a_n = c_3 + c_4n$

since, $(n + 1)$ is polynomial of degree 1.

Substituting in the given equation, we get:

$c_3 + c_4(n + 2) + 2(c_3 + c_4(n + 1)) + c_3 + c_4n = n + 1$

Comparing the corresponding coefficients, we get: $c_4 = 1/4$ and $c_3 = 0$.

Therefore, $a_n^{(p)} = n / 4$

Hence, the solution, would be:

$a_n = (c_1 + c_2n)(-1)^n + n / 4$

But the solution in textbook is

$a_n = (c_1 + c_2n)(-1)^n + 1/6(2n - 1)$

Please explain me where I am going wrong.

Thanks!

Alfarhan Zahedi
  • 43
  • 2
    It doesn't appear as though you have made a mistake at all. Rather, it appears as though the book's answer is the incorrect one here. That, or perhaps the transcription of the problem is where the mistake is. In any case, checking manually by hand as well as checking calculators like wolframalpha give the same answer as yours for the problem stated. Keep up the good work. – JMoravitz Nov 28 '17 at 15:05
  • Okay. Thanks for the feedback. I also thought the answer was wrong, but had to be sure as I am new to recurrence relations. Thanks a lot! – Alfarhan Zahedi Nov 28 '17 at 15:08

2 Answers2

1

I have verified your results using a slightly different method. Here I reduce the original recurrence to a more familiar one with a known solution. Thus consider

$$a_{n+2} + 2a_{n+1} + a_{n} = 1+n$$

Let $a_{n}=f_n+pn+q$, so that

$$ \begin{align} &f_{n+2}+p(n+2)+q+\\ &2f_{n+1}+2p(n+1)+2q+\\ &f_{n}+pn+q=1+n \end{align} $$

Now chose $p$ and $q$ so that those terms vanish, to wit,

$$ p=\frac{1}{4}\\ q=0; $$

So that we are left with

$$f_n=-2f_{n-1}-f_{n-2}$$

with characteristic roots $(-1,-1)$ and a solution given by

$$f_n=\left(nf_1+(n-1)f_0\right)(-1)^{n-1}$$

where $f_0=a_0$ and $f_1=a_1-p$. The complete solution is then given by

$$a_n=f_n+pn$$

I have verified this solution for arbitrary values of $a_0$ and $a_1$.

Cye Waldman
  • 7,524
1

General technique uses generating functions. Define:

$\begin{equation*} A(z) = \sum_{n \ge 0} a_n z^n \end{equation*}$

Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:

$\begin{align*} \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 &= \sum_{n \ge 1} z^n + \sum_{n \ge 0} n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} + 2 \frac{A(z) - a_0}{z} + A(z) &= \frac{1}{1 - z} + z \frac{d}{d z} \frac{1}{1 - z} \\ &= \frac{1}{1 - z} + \frac{z}{(1 - z)^2} \end{align*}$

Solve for $A(z)$, split into partial fractions:

$\begin{equation*} A(z) = -\frac{4 a_1 + 4 a_0 - 1}{(1 + z)^2} + \frac{\frac{4 a_1 + 8 a_0 - 1}{(1 + z)} + \frac{1}{4 (1 - z)^2} - \frac{1}{4 (1 - z)} \end{equation*}$

Note that:

$\begin{align*} (1 - \alpha z)^{-m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} \alpha^n \zeta^n \\ &= \sum_{n \ge 0} \binom{m + n - 1}{m - 1} \alpha^n z^n \end{align*}$

Also:

$\begin{align*} \binom{n + 1}{1} &= n + 1 \\ \binom{n + 0}{0} &= 1 \end{align*}$

and you can read off the coefficients. The solution here has the form:

$\begin{equation*} a_n = (-1)^n c_1 n + (-1)^n c_2 + c_3 n + c_4 \end{equation*}$

vonbrand
  • 27,812