# 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)?