Characteristic Equation Problem

Question

Let $a(1)= 1,\ a(2)= 5,\ a(n+2) = a(n+1)+2a(n)+3\ (n\in \mathbb{N})$. Find a formula for $a(n)$ in terms of $n$.

I tried to solve this problem by finding a pattern in each of the terms, but I was unsuccessful in any such attempts. Does anyone know the correct way to solve this?

Answer 1

You have $$\begin{pmatrix}a_{n+2} \\ a_{n+1} \\1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}\begin{pmatrix}a_{n+1} \\ a_{n} \\1 \end{pmatrix} $$ so that $$ \begin{pmatrix}a_{n+2} \\ a_{n+1} \\1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}^n\begin{pmatrix}5 \\ 1 \\1 \end{pmatrix}$$ and then diagonalizing gives $$ \begin{pmatrix}a_{n+2} \\ a_{n+1} \\1 \end{pmatrix} = \begin{pmatrix} -1 & -3 & 2 \\ 1 & -3 & 1 \\ 0 & 2 & 0\end{pmatrix}\begin{pmatrix} -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2\end{pmatrix}^n\begin{pmatrix} -1 & -3 & 2 \\ 1 & -3 & 1 \\ 0 & 2 & 0\end{pmatrix}^{-1}\begin{pmatrix}5 \\ 1 \\1 \end{pmatrix}$$ and then multiplying this out gives $$ \begin{pmatrix}a_{n+2} \\ a_{n+1} \\1 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} \left(-3+(-1)^n+3 \cdot 2^{n+2} \right) \\ \frac{1}{2} \left(-3+(-1)^{n+1}+3 \cdot 2^{n+1} \right) \\ 1\end{pmatrix}$$ so that we finally get the closed form solution $$\boxed{a_n =\left.\left.\frac{1}{2} \right[3 \cdot 2^n-3+(-1)^n \right]} $$

Answer 2

So, we have an equation $a(n) = a(n-1) + 2a(n-2) + 3$, for $n \ge 3$, and $a(1)=1,a(2)=5$.

Let's focus on homogenous equation: $a(n) = a(n-1) +2a(n-2)$

It's characteristic polynomial $w(\lambda) = \lambda^2 - \lambda -2 = (\lambda-2)(\lambda+1)$ has roots $-1,2$ of degree $1$, so that we should seek solution to our homogenous equation in the form $a(n) = A\cdot (-1)^n + B\cdot 2^n$

But, we must deal with non-homogenous equation, precisely: $a(n) = a(n-1) + 2a(n-2) + 1^n \cdot f(n) $, where $f$ is polynomial of degree $0$, and due to that part, we have to deal with solution of form:

$a(n) = A\cdot (-1)^n + B\cdot 2^n + C \cdot 1^n $ We have $3$ variables, so we need $3$ values $a(1),a(2),a(3)$. The first and the second we already know, and $a(3) = a(2) + 2a(1) + 3 = 5 + 2 + 3 =10$

So we have $3$ linear equations:

$a(1) = -A + 2B + C$

$a(2) = A + 4B + C$

$a(3) = -A + 8B + C$

Solving it, we get $B = \frac{3}{2}$, $C=-\frac{3}{2}$, $A=\frac{1}{2}$

And our formula for function $a$ is: $a(n) = \frac{(-1)^n + 3\cdot 2^n - 3}{2}$, $n \in \mathbb N$