Proof by Strong Induction for $a_k = 2~a_{k-1} + 3~a_{k-2}$ $$\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. 
 A: *

*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.
A: 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
A: 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.
