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


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:




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

$r^2=rc_1 + c_2$




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

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


2 Answers 2


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$.

  • $\begingroup$ 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$ ? $\endgroup$
    – 0x6C38
    Commented Jun 23, 2015 at 1:42
  • $\begingroup$ The OP edited the question and fixed the recurrence. $\endgroup$
    – lhf
    Commented Jun 23, 2015 at 2:25
  • $\begingroup$ @lhf I noticed that but then it would be $24 + 12 -4 \neq 0$ which still doesn't match right? $\endgroup$
    – 0x6C38
    Commented Jun 23, 2015 at 2:29
  • $\begingroup$ @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. $\endgroup$
    – TravisJ
    Commented Jun 23, 2015 at 3:36
  • $\begingroup$ @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? $\endgroup$
    – 0x6C38
    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$.

  • $\begingroup$ $-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? $\endgroup$
    – 0x6C38
    Commented Jun 23, 2015 at 2:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .