# 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:

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.

• Use the underscore. \$C_{k-3}\$ will render as $C_{k-3}$ – fleablood Nov 4 '19 at 3:33
• Strong induction allows (if you need it) i) multiple base cases ii) an induction step that isn't an increase by one but an increase by any other useful jump. – fleablood Nov 4 '19 at 3:42

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.

• Thanks a lot for both clarifying my question, and providing an answer. Embarrassingly I must say I am still trying to interpret these answers, which shows I need to do much more review over strong mathematical induction. If you don't mind answering this last question, how do I even interpret these "subset" numbers. Sorry if this makes no sense, but I have never really dealt with this "underscore" syntax, as evident by me not being able to describe it. I envy your understanding – skepticalforever Nov 4 '19 at 4:16
• We all started somewhere, don’t worry. As for the syntax, interpret it as just an indexed sequence of variables. $c_0$ is the zeroth variable, $c_1$ is the first, and so on. Other than the fact that you can reference a particular variable by a single whole number, you shouldn’t treat them any different than any other variable name. – ViHdzP Nov 4 '19 at 4:22
• Again, thanks a lot :) – skepticalforever Nov 4 '19 at 4:32

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

• Very good explanations! – skepticalforever Nov 4 '19 at 5:22