Solving Strong Mathematical Induction Sequence I'm trying to work on the problem below, though I've hit a wall on how to proceed to prove the inductive step.
Suppose that $c_0,c_1,c_2\ldots$ is a sequence defined as follows: $$c_0=2,\, c_1=2,\, c_2=6,\, c_k=3c_{k-3}\,(k\geq3)$$
Prove that $c_n$ is even for each integer $n\geq0$.
Here is what I have so far:


*

*Show that $P(0)$ and $P(1)$ are true.


*

*$c_0=2$ and $2\geq0$ and $2\mid2$, so this is even.

*$c_1=2$ and $2\geq0$ and $2\mid2$, so this is even.


*Show that for every integer $k\geq1$, if $P(i)$ is true for each integer $i$ with $0\leq i\leq k$, then $P(k+1)$ is true.


*

*Let $k$ be any integer with $k\geq1$, and suppose $c_i$ is even for each integer $i$ with $0\leq i\leq k$ [inductive hypothesis].

*I must show that $c_{k+1}$ is even for each integer $k\geq0$.

*Now $c_{k+1}=3c_{k-2}$...



...and this is where I do not understand how to proceed. Any tips on how I can finish solving this problem are greatly appreciated.
 A: Let $P(n)$ be the statement “$c_n$, $c_{n+1}$, $c_{n+2}$ are even”. We have $P(0)$ by assumption. Furthermore, $P(n)\Rightarrow P(n+1)$, since if $c_n$, $c_{n+1}$, $c_{n+2}$ are even, $c_{n+3}=3c_n$ must be even also. By induction, $P(n)$ is true for all $n$, which implies immediately that $c_n$ must be even for all $n$.
A more immediate solution would be to use @fleablood’s approach, but this one enables you to do this problem by pure, vanilla induction.
A: Don't use $P(n)\implies P(n+1)$ in your induction step.  Do $P(n)\implies P(n+3)$ (and that is trivial)
This is acceptable.
As $C_0$ is even then by induction $C_{3k}$ is even for all $k\in \mathbb N$.
And as $C_1$ is even then by induction $C_{1 + 3k}$ is even for all $k\in \mathbb N$.
And as $C_2$ is even then by induction $C_{2 + 3k}$ is even for all $k\in \mathbb N$.
So as any $n\in \mathbb N$ is either equal to $0,1,$ or $2$ plus some multiple of $3$ we are done.
.....
Assuming we have proven that $C_{n}$ is even means $C_{n+3}$ is even.  I leave that to you.  (Again... it is trivial.)
==========
Alternative explanation.
"Strong" induction means in the induction step you don't just assume $P(n)$ is true for $n=k$ but $P(n)$ is true for all $n \le k$.
So in this induction step:
Assume $C_n$ is even for all $n \le k$.  We must prove that $C_{k+1}$ is even.
And here it is:
$C_{k+1} = 3\times C_{k-2}$ and $k-2 < k$ so $C_{k-2}$ is even.  So $C_{k+1}$ is a multiple of an even number and is even.
That's it.  And that's fair.
In "weak" induction, we would have done something directly related to $C_k$.  But in "strong" induction we don't have to use $C_k$, we can use $C_{\text{anything less than or equal to }k}$.  In this case we use $C_{k-2}$.
