How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation:

$8a_{n+2}+4a_{n+1}-4a_n=0$

I need to determine if these are possible solutions, and in that case, which initial conditions do they require:

• $a_n = 3(-1)^n$
• $a_n = 3(-1/2)^n + 1$
• $a_n = 7(1/2)^n$

I know this is a second degree linear recurrence so I've tried to reach a generic solution:

$8a_{n+2}+4a_{n+1}-4a_n=0$

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

$r^n=c_1r^{n+1}+c_2r^{n+1}$

Dividing by $r^{n-2}$:

$r^2=rc_1 + c_2$

$0=-1r^2+2r+1$

$r_1=1-\sqrt{2}$

$r_2=1+\sqrt{2}$

$a_n=\alpha_1 r_{1}^{n} + \alpha_2 r_{2}^n$

But I don't know how to continue...

Hint: plug in what you are given $(a_{n})$ and see if it satisfies the recurrence. If it does, then compute $a_{0}$, $a_{1}$ and $a_{2}$ as your initial conditions. For example, if $a_{n}=3(-1)^{n}$ what we check is:

$8(3(-1)^{n+2})+4(3(-1)^{n+1})4(3(-1)^{n})=24(-1)^{n+2}+144(-1)^{2n+1}=-144\pm 24 \neq 0$ so the first case is not possible.

EDIT: Now that the recurrence has been edited to $8a_{n+2}+4a_{n+1}-4a_{n}=0$... we would have:

\begin{align*} 8(3(-1)^{n+2})+4(3(-1)^{n+1})-4(3(-1)^{n}) &= 24(-1)^{n+2}+4(3(-1)^{n+1})+4(-1)(3(-1)^{n}) \\ &= 24(-1)^{n+2}+12(-1)^{n+1}+12(-1)^{n+1} \\ &= 24(-1)^{n+2}+24(-1)^{n+1}=0 \end{align*}

so the $3(-1)^{n}$ does satisfy the recurrence and the initial conditions are $a_{0}=3(-1)^{0}=3$, $a_{1}=3(-1)^{1}=-3$ and $a_{2}=3$.

• why does $-144\pm 24 \neq 0$ mean that $24(-1)^{n+2}+144(-1)^{2n+1} \neq 0$ what if $2n+1=0$ and $n+2=0$ ? Commented Jun 23, 2015 at 1:42
• The OP edited the question and fixed the recurrence.
– lhf
Commented Jun 23, 2015 at 2:25
• @lhf I noticed that but then it would be $24 + 12 -4 \neq 0$ which still doesn't match right? Commented Jun 23, 2015 at 2:29
• @MrD, sorry, this specific example was for the recurrence where the last two terms were multiplied together (I guess there was an edit). Note that $2n+1$ is always odd so $(-1)^{2n+1}=-1$. So the $144(-1)^{2n+1}=-144$ for all $n$... $24(-1)^{n+2}$ is either $\pm 24$. Either way, when you combine them you don't get zero. Commented Jun 23, 2015 at 3:36
• @TravisJ Thank you for being so patient. In your updated answer you wrote $24(-1)^{n+2}+4(3(-1)^{n+1})+4(3(-1)^{n+1})$ instead of $24(-1)^{n+2}+4(3(-1)^{n+1})+4(3(-1)^{n})$ Was that a typo or am I missing something huge? Commented Jun 23, 2015 at 3:47

You can either test directly whether the given expressions satisfy the recurrence or you can test whether $-1$, $-1/2$, $1/2$ are roots of the characteristic equation $8r^2+4r-4=0$.

• $-1$ is a root for $8r^2+4r−4=0$ however, if the other answer is correct, then $a_n=3(−1)^n$ doesn't satisfy the recurrence... which one of you is correct? Commented Jun 23, 2015 at 2:18