$$\begin{align} a_0 &= 1 \\ a_1 &= 1 \\ a_k &= 2~a_{k-1} + 3~a_{k-2} \quad \text{ for } k \ge 2 \end{align}$$

Proof by Strong Induction: For all non-negative integers $n$, $a_n$ is an odd integer.

Proof by Strong Induction:

$$\begin{align} P(n) &= a_n \text{ is an odd integer } \\ P(0) &= a_0 \text{ is an odd integer } \\ \end{align}$$

Assume $P(n)$, show $P(n+1)$

Basis Step: $P(0)$, $P(1)$, $P(2)$, $P(3)$, $P(4)$, $P(5)$

Inductive Step: Want to show for all integers $n \ge 5$, if $P(i)$ is true for all $0 < i < n$, then $P(n)$ is true

Let $c > 5$, be arbitrary and fixed

IH: Assume $P(i)$ for any $0<i<c$

I don't know where to go in the proof from here. Can anybody help me show that $P(i)$ is always odd, I am confused with strong induction, too many variables are introduced.

  • 1
    $\begingroup$ The idea is that since $a_{k-2}$ is odd, $2a_{k-1}+3a_{k-2}$ is an even number plus $3$ times an odd number, so it is odd. $\endgroup$ – André Nicolas Apr 4 '15 at 15:34
  • $\begingroup$ Strong induction does not have a base case. It is simply the $n=0$ case of the inductive step. The $c$ in the inductive hypothesis should be an $n$, and stating the inductive hypothesis redundant, you already stated it when you wrote the "inductive step". $\endgroup$ – DanielV Apr 4 '15 at 16:06

For example, $\,a_0 = 1 = a_1\,$ are both odd so $\,a_2 = 2a_1 + 3a_0\,$ = even + odd = odd. That is precisely how the general induction step is proved, i.e. for $\,k\ge 2\,$ prove in the same way that $\,a_k\,$ is odd, given that, by (strong) induction hypothesis, both $\,a_{k-1}\,$ and $\,a_{k-2}\,$ are odd.

Remark $\ $ Insight is gained by viewing things mod $2.\,$ Then the recurrence reduces to simply $\, a_k \equiv a_{k-2},\,$ so by induction $\,a_{2n} \equiv \color{#c00}{a_0}\,$ and $\,a_{2n+1}\equiv \color{#c00}{a_1}.\,$ But both base cases $\,\color{#c00}{a_0,a_1}$ are $\equiv 1.$

If instead $\,a_0\equiv 0,\ a_1\equiv 1\,$ then, since $\,a_{n}\equiv a_{n\ {\rm mod}\ 2},\,$ we get $\,a_n\,$ is even $\iff n\,$ is even

  • IH the induction hypothesis is $p(i)$ is true for any :$0< i< c$
  • Goal we want to prove that $P(c)$ is true

We can use : $$a_c=\underbrace{2a_{c-1}}_{\text{even}}+\underbrace{3a_{c-2}}_{\text{odd}} $$

and IH implies that both $a_{c-2}$ and $a_{c-1}$ are odd so $a_{c}$ is odd hence $P(c)$ is true.


You verified the base step and you have the induction assumption. Here's how you can use it: $$ a_{k+1}=\underbrace{2a_{k}}_{\text{even times odd is even}}+\underbrace{3a_{k-1}}_{\text{odd times odd is odd}} $$ Since an even number plus an odd number is an odd number, this proves your result. Note that strong induction was necessary to conclude that $a_{k-1}$ was odd. That's really all you need.


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.