# Solution

Suppose a function $f(n)$ is defined in the following way: $f(1)=1$, $f(2)=5$, and for $n \ge 2$, $f(n+1)=f(n)+2f(n-1)$. Conjecture a formula for $f(n)$, assuming $n$ is always a natural number (i.e., positive integer), and prove your conjecture.

Consider the first several values of $f(n)$,

 $n$ 1 2 3 4 5 6 7 8 9 10 $f(n)$ 1 5 7 17 31 65 127 257 511 1025

It appears that $f(n) = 2^n + (-1)^n$. Let us show this by the second principle of induction (i.e., strong induction).

The above table verifies the basis step, so it remains to consider the inductive step.

Using strong induction, we need to show that if $f(n) = 2^n + (-1)^n$ for all $n \le k$ for some integer $k$, then $f(k+1) = 2^{k+1} + (-1)^{k+1}$.

At this point the argument is direct:

$$\begin{array}{rcl} f(k+1) &=& f(k) + 2 f(k-1)\\ &=& \left[ 2^k + (-1)^k \right] + 2 \cdot \left[ 2^{k-1} + (-1)^{k-1}\right]\\ &=& 2^k + (-1)^k + 2^k - 2(-1)^k\\ &=& 2 \cdot 2^k - (-1)^k\\ &=& 2^{k+1} + (-1)^{k+1} \end{array}$$

Hence, by the second principle of mathematical induction, $f(n) = 2^n + (-1)^n$ for all positive integers $n$.