Induction problem 1

Here is the definition of g, for reference:

g(0) = 2

g(1) = 7

g(k) = g(k-1) + 2g(k-2), for \(k\ge 2\)

Solution

Proof: By induction on n.

Base case(s): For n=0, we have \(3\cdot2^0 + (-1)^{1} = 3 (-1) = 2\) which is equal to g(0).

For n=1, we have \(3\cdot2^1 + (-1)^{2} = 6 +1 = 7\) which is equal to g(1).

Inductive hypothesis: Suppose that \(g(n) = 3\cdot2^n + (-1)^{n+1}\) for all integers \(n = 0,1, \ldots, k-1\) (where k is an integer \( \ge 2\)).

Rest of the inductive step: Using the definition of f and then the inductive hypothesis, we get

\( \begin{eqnarray} g(k) &=& g(k-1) + 2g(k-2) \\ &=& (3\cdot2^{k-1} + (-1)^{k})\ \ +\ \ 2(3\cdot2^{k-2} + (-1)^{k-1}) \end{eqnarray} \)

Simplifying this, we get that

\( \begin{eqnarray} g(k) &=& (3\cdot2^{k-1} + (-1)^{k})\ \ +\ \ 3\cdot2^{k-1} + 2(-1)^{k-1} \\ &=& 3\cdot 2 \cdot2^{k-1} + (-1)^{k} - 2(-1)^{k} \\ &=& 3\cdot2^{k} - (-1)^{k} \\ &=& 3\cdot2^{k} + (-1)^{k+1} \end{eqnarray} \)

So \(g(k)= 3\cdot2^{k} + (-1)^{k+1}\), which is what we needed to show.

Self-check

Does your inductive step use the inductive hypothesis twice, once for g(k-1) and once for g(k-2)?