Solving Strong Mathematical Induction Sequence

Question

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:

1. 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.

2. 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.

Answer 1

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.

Answer 2

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}$.