Solve the recurrence $T(n) = T(n-1) + 2T(n-2) + 2$

Question

$T(0) = 1, T(1) = 0$

I ain't able to get answer from any of the methods.

Substitution:

$T(n) = x^n $

\begin{align} & x^n = x^{n-1} + 2x^{n-2} + 2 \\ & x^2 = x + 2 + 2x^2\\ & x^2 + x + 2 =0 \end{align}

solving this I will get a complex root.

\begin{align} x & = \frac{-1 \pm \sqrt{1-8}}{2} x & = \frac{-1 \pm 7i}{2} \end{align}

Now how to go further.

General:

\begin{align} T(2) & = 4\\ T(3) & = 6\\ T(4) & = 16\\ T(5) & = 30\\ T(6) & = 64\\ T(7) & = 126\\ T(8) & = 256 \end{align}

From this i can deduce if $n$ is even then $2^n$. I cant deduce for if $n$ is odd.

Answer 1

Put $U(n) - 1 = T(n)$ and the equation is $$ U(n+2) = U(n-1) + 2U(n) $$ let as you do $U(n) = x^n$ and we get $$ x^{n+2} = x^{n-1}+2x^n $$ or we need to solve $$ x^2-x-2 = 0 $$

hence $$ x = \frac{1}{2} \pm \sqrt{1/4+8/4} = \frac{1 \pm 3}{2} $$

So $$ U(n) = A 2^n + B (-1)^n $$ and $$ T(n) = A 2^n + B (-1)^n - 1 $$ So $$ T(0) = A+B-1 = 1 $$ and $$ T(1) = 2A-B -1 = 0 $$ gives $$ A = 1, \,B=1 $$ And we conclude $$ T(n) = 2^n+(-1)^n-1 $$

Answer 2

Hint try to make it homogeneous, from $$T(n) = T(n-1) + 2T(n-2) + 2$$ $$T(n+1) = T(n) + 2T(n-1) + 2$$ we have $$T(n)-T(n+1)=T(n-1) + 2T(n-2) - T(n) - 2T(n-1) \iff \\ T(n+1)-2T(n)-T(n-1)+2T(n-2)=0$$ leading to characteristic polynomial $$x^3-2x^2-x+2=0 \iff (x-2)(x-1)(x+1)=0$$

Answer 3

Another way to solve the problem: note that you have

$$ \begin{bmatrix} a_{n+1}\\ a_n \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n}\\ a_{n-1} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$