How do i prove a recursion with $ a_n = 3 \cdot 2^{(n-1)} + 2(-1)^n $ so that for all $ n \in \mathbb{N} $ it is true?

Question

I am pretty new when it comes to recursion together with induction. I would appreciate if somebody could show me how to approach this kind of problem: $$ a_n = \begin{cases} 1 & \text{if $n=1$} \\ 8 & \text{if $n=2$} \\ a_{n-1}+2\cdot a_{n-2} & \text{if $ n \in \mathbb{N}\setminus \left\{1,2 \right\}$} \end{cases} $$

Proof by induction that $$ a_n = 3 \cdot 2^{(n-1)} + 2(-1)^n $$ is true for all
$$ n \in \mathbb{N} $$

I would really appreciate some examples, as i am having a hard time to understand how to approach this (even though i do understand induction and how to use it properly, the recursion just gives me a hard time).

Thanks for taking your time!

Answer 1

We have as base cases that $a_1 = 3\cdot 2^{1-1} +2(-1)^1=3-2 = 1$ and Then $a_2 = 3\cdot 2^{2-1} + 2(-1)^2 = 6+2=8$.

So we just need to prove the induction step that if

$a_{n-1} = 3\cdot 2^{n-2} + 2(-2)^{n-1}$ and $a_n = 3\cdot 2^{n-1} + 2(-1)^n$ that that would mean

$a_{n+1} = 3\cdot 2^{n} + 2(-1)^{n+1}$.

And we have $a_{n+1} = a_{n-1} +2a_{n-2}$ by definitions so substituting:

$a_{n+1} = [3\cdot 2^{n-1} + 2(-1)^n] + 2[3\cdot 2^{n-2} + 2(-1)^{n-1}]$. So just do algebra

$= [3\cdot 2^{n-1} + 2(-1)^n] + [2\cdot 3\cdot 2^{n-2}+ 2\cdot 2(-1)^{n-1}]=$

$= [3\cdot 2^{n-1} + 2(-1)^n] + [3\cdot 2^{n-1} + 2\cdot 2(-1)^{n-1}]=$

$=(3\cdot 2^{n-1} + 3\cdot 2^{n-1}) + (2(-1)^n + 2\cdot 2(-1)^{n-1}]=$

$=2\cdot 3\cdot 2^{n-1} + 2(-1)^{n-1}(2-1)=$

$3\cdot 2^{n} + 2(-1)^{n-1}=$

$3\cdot 2^n + 2(-1)^{n-1}\cdot (-1)^2 = $

$3\cdot 2^n + 2(-1)^{n+1}$.

.....

It might be easier instead of writing $(-1)^m$ to write $\pm 1_{m;even/odd}$

Then $a_{n+1} = [3\cdot 2^{n-1} \pm 2] + 2[3\cdot 2^{n-2} \mp 2]=$ ($\pm = +$ if $n$ is even and $\pm = -$ if $n$ is odd; $\mp$ is the exact opposite.)

$[3\cdot 2^{n-1} + 2\cdot 3\cdot 2^{n-2}] + [\pm 2 \mp 2\cdot 2]=$

$[3\cdot 2^{n-1} + 3\cdot 2^{n-1}] + [\pm 2 \mp 4]=$

$2\cdot3\cdot 2^{n-1} \mp 2=$ ($\mp=-$ if $n$ is even or in other words if $n+1$ is odd and $\mp = +$ if $n +1$ is even.)

$3\cdot 2^n + (-1)^{n+1} 2=$

Answer 2

Start with the base cases. Clearly for $n=1,2$

$a_1 = 1 = 3\cdot 2^{1-1}+2(-1)^1=3-2=1$

$a_2 = 8 = 3\cdot 2^{2-1}+2(-1)^2=3\cdot 2+2=8$

Suppose the statement is true for $n$. Thus:

$$a_{n+1}=a_n+2a_{n-1}=(\text {here we use our assumption})=3⋅2^{(n−1)}+2(−1)^n+2(3⋅2^{(n−2)}+2(−1)^{n-1})=3⋅2^{(n−1)}+2(−1)^n+3⋅2^{(n−1)}+2\cdot2(−1)^{n-1}=3\cdot2^n+2(-1)^n$$

So, using induction we showed that the statement holds for all $n \in \mathbb{N} $

Answer 3

Taking a general view:

It is easy to verify that both $2^n$ and $(-1)^n$ satisfy the recursion $$a_n=a_{n-1}+2a_{n-2}$$

It follows quickly that any linear combination of them, as in $A\times 2^n+B\times (-1)^n$ will also satisfy that recursion (where $A,B$ are constants). In particular, your sequence, $A_n=\frac 32\times 2^n+2\times (-1)^n$, satisfies the desired recursion.

We can also confirm, directly, that $A_1=1, A_2=8$, so the sequence $A_n$ has the right initial conditions and it satisfies the given recursion.

Now for the inductive step: If two sequences, $A_n, B_n$ have the same initial conditions and satisfy the same recursion, they must coincide. Indeed, we have already checked that $A_n=a_n$ for $n=1,2$. Let us suppose that we have checked equality up to $n-1$. In particular, we assume that we know $A_{n-2}=a_{n-2}$ and $A_{n-1}=a_{n-1}$. But then the recursion implies that $A_n=a_n$ and we are done.

Worth noting: we could have "guessed" this recursion by considering the quadratic with roots $2, -1$. Namely $$f(x)=(x-2)(x+1)=x^2-x-2$$ In general, the quadratic $p(x)=x^2+Ax+B$ is associated with the linear recursion $a_n=-Aa_{n-1}-Ba_{n-2}$, meaning that the solution to the recursion has the form $C_1\times r_1^n+C_2\times r_2^n$ where $r_1,r_2$ are the roots of the quadratic. (the case where $r_1=r_2$ is special, but not needed here).