4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Use the underscore. \$C_{k-3}\$ will render as $C_{k-3}$ $\endgroup$ – fleablood Nov 4 '19 at 3:33
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 4 '19 at 3:42
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – skepticalforever Nov 4 '19 at 4:16
  • 2
    $\begingroup$ 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. $\endgroup$ – URL Nov 4 '19 at 4:22
  • 1
    $\begingroup$ Again, thanks a lot :) $\endgroup$ – skepticalforever Nov 4 '19 at 4:32
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very good explanations! $\endgroup$ – skepticalforever Nov 4 '19 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.