Induction proof $a_n$ is even for n $\ge$ 1

Question

$$a_1=0, a_2=2, a_3=2, ... a_k = a_{k-2}+3a_{k-3}$$ for k $\ge$ 4

Initial case n = 1 given above it is true as zero is divisible by 2.

Let n = k. Assume that $a_{k+1} = a_{k-2+1}+3a_{k-3+1} $

That is $a_{k+1} = a_{k-1}+3a_{k-2} $

How to prove by induction that $a_n$ is even for n $\ge$ 1

Answer 1

Use strong induction on $n \geq 1$.

Check the base case: $n = 1$, then $a_1 = 0 = 0\cdot 2$: even

Supposed the claim is true for all $k < n$, that is: $2|a_k$ for $k < n$, you need to show:

$2|a_n$.

Since $n - 2 < n$, and $n - 3 < n$, the induction hypothesis states that: $2|a_{n-2}$ and also $2|a_{n-3}$, so $2|(a_{n-2} + 3\cdot a_{n-3}) = a_n$.

So: $2|a_n$ ,$\forall n \geq 1$

Answer 2

All $a_i$ for $i\in\{1,2,3\}$ are even. Note that sum of even is even.

Answer 3

Let $a_i=2.b_i$ for all $i<k$, then $a_k=a_{k-2}+3.a_{k-3}=2.b_{k-2}+2.3.b_{k-3}=2.b_k$.