The question: The terms of a sequence are given recursively as \begin{cases} a_0 = 1,\\ a_1 = 1 \\a_n=2a_{n-1} + 3a_{n-2} \quad\text{ for } n \geq 2 \end{cases} prove by mathematical induction $a_n = \frac12(3^n) +\frac12(-1)^n$ for all $n \geq 0$

I've started by proving that the formula works e.g
$$a_0= 1\implies a_0 = \frac12(3^0)+\frac12(-1)^0 = 1 \\a_1=1\implies a_1 = \frac12(3^1) + \frac12(-1)^{1} = 1$$

Therefore $p(1)$ and $p(2)$ are true

Now I have to do the hard part.. the inductive step suppose $p(1), p(2),\ldots, p(k)$, that is $a_{k+1} = 2a_{k} + 3a_{k-1}$ Im not sure where to really go from here.

  • $\begingroup$ For $n=2$ we have $a_2 = 2a_1+3a_0=2+3=5$, and $a_n = 1/2(3^n) +1/2(-1)^n = 10/2 =5$ for $n=2$ : fine. For the induction step (from $k$ to $k+1$) we assume that the relation holds for $a_k$ and $a_{k-1}$ and we have to prove it for $a_{k+1}$. $\endgroup$ Sep 11 '14 at 12:54

We have, by induction hypotheses, that :

$a_k=\frac 12(3^k)+\frac 12(-1)^k$

and :

$a_{k-1}=\frac 12(3^{k-1})+\frac 12(-1)^{k-1}$.

If we "plug them" into :


we get :

$$a_{k+1}=2\left[\frac 12(3^k)+ \frac 12(-1)^k\right]+3\left[\frac 12(3^{k-1})+ \frac 12(-1)^{k-1}\right] =$$

$$= 3^k+(-1)^k+3 \frac 12 3^{k-1}+ \frac 32(-1)^{k-1} =$$

$$=3^k+ \frac 12 3^k+(-1)(-1)^{k-1}+ \frac 32(-1)^{k-1}=\frac 32 3^k+ \frac 12 (-1)^{k-1}=$$

$$=\frac 12 3^{k+1}+ \frac 12 (-1)^{k-1}=\frac 12 3^{k+1}+ \frac 12 (-1)^{k-1}(-1)^2=$$

$$=\frac 12 3^{k+1}+ \frac 12 (-1)^{k+1}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.