Inductively showing $g(s) = 3(g(s-1)+g(s-2))+1$ is odd for all $s$

Question

How would I show this equation is odd by using the induction hypothesis: $$ g(s) = 3(g(s-1))+(g(s-2))+1 $$ I was thinking that I would prove $g(s)$ is odd by $g(s+1) = 3(g(s)+g(s-1))+1$.

How would I proceed using the induction hypothesis?

Answer 1

The first step is to check the hypothesis for eg. $s=0$ and $s=1$ depending on the starting condition. That is, we check if the first two values are odd.

Then we assume that $g(s)$ is odd for all $s\in\mathbb{Z}$, where $s\leq k$. This is our induction hypothesis. Like you write, we have \begin{align*} g(k+1)=3\big(g(k)+g(k-1)\big)+1. \end{align*}

Can you see how we may use the induction hypothesis now?

Solution:

From the induction hypothesis, both $g(k)$ and $g(k-1)$ are odd, so $3\big(g(k)+g(k-1)\big)$ is even. Thus, $g(k+1)$ must be odd.