Proof by Strong Induction (solution of linear recurrence)

Question

$a_0 = 1, a_1 = 1, a_k = 2a_{k-1} + 2a_{k-2}$ for $k≥2$

For all integers $n≥0$, $a_n= \frac{1}2[3^{n}+(-1)^n$]

Proof By Strong Induction:

Basis:

$F(0), F(1), F(2), F(3), F(4), F(5)$

Inductive Step:

Let $c ≥ 0$, be arbitrary and fixed.

IH:

Assume for all integers $c, 0 < n < c, F_c$ is an integer and $F_c = (1/2)3^c+(-1)^c$

By definition $F_c = 2a_{c-1} + 2a_{c-2}$ for $c≥2$

I do not know how to finish the proof because I am starting to introduce to many integers / variables and I am getting confused. How do I complete the proof?

Answer 1

Basis step:

It's clear that:

• $F(0)$ is an integer and $F(0)=\frac{3^0+(-1)^0}{2}$
• $F(1)$ is an aninteger and $F(1)$=\frac{3^1+(-1)^1}{2}$

Induction steps

Given an integer $n$, Assume that for every $0\leq k\leq n$ we have:

• $F(k)$ is an integer and $F(k)=\frac{3^k+(-1)^k}{2}$

And let's prove this assertion for $n+1$, we have $n\leq n$ and $n-1\leq n$ so by the induction hypothesis:

• $F(n)$ is an integer and $F(n)=\frac{3^n+(-1)^n}{2}$
• $F(n-1)$ is an integer and $F(n-1)=\frac{3^{n-1}+(-1)^{n-1}}{2}$

and by definition $F(n+1)=2F(n)+3F(n-1))$ so : F(n+1) is an integer and $$\begin{align} F(n+1)&=2.\frac{3^n+(-1)^n}{2}+3.\frac{3^{n-1}+(-1)^{n-1}}{2} \\ &=\frac{2.3^n+3.3^{n-1}-2.(-1)^{n+1}+3.(-1)^{n+1}}{2}\\ &=\frac{3^{n+1}+(-1)^{n+1}}{2}\end{align}$$

and here the induction terminates!