# 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}$ Nov 4, 2019 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. Nov 4, 2019 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 Nov 4, 2019 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. Nov 4, 2019 at 4:22
• Again, thanks a lot :) Nov 4, 2019 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! Nov 4, 2019 at 5:22