# how do I prove this by induction? (recursion)

The terms are given recursively: $P_0=3$ $P_1=7$ and $P_n = 3P_{n-1}-2P_{n-2}$ for $n\ge2$

What should I assume and what step proves that $P_n=2^{n+2}-1$ is a closed form of the sequence.

Suppose $n_0=1$ and the base cases are $0$ and $1$.

I think this book has a mistake

problem from the book

• The book has not made a mistake: wolframalpha.com/input/… – parsiad Apr 6 '16 at 20:37
• If you want a straight check: we have $3P_{n-1}-2P_{n-2}=3\times 2^{n+1}-3-2\times 2^n+2=6\times 2^{n}-2 \times 2^n-1=4\times 2^n-1=2^{n+2}-1=P_n$. – lulu Apr 6 '16 at 20:39
• $P_n=3P_{n-1}-2P_{n-2}$ has corresponding characteristic polynomial $x^2-3x+2$ which factors as $(x-2)(x-1)$ and thus you will have $P_n = \alpha\cdot 2^n + \beta\cdot 1^n$ for some appropriate values of $\alpha$ and $\beta$ which are found using the initial conditions. – JMoravitz Apr 6 '16 at 20:39

Note that $2^{0+2}-1=2^{2}-1=4-1=3$ and $2^{1+2}-1=2^{3}-1=8-1=7$, so that the base case holds. Suppose now that the statement holds for $P_{n-1}$ and $P_{n-2}$ and note that \begin{align*} P_{n} & =3P_{n-1}-2P_{n-2}\\ & =3\left(2^{n+1}-1\right)-2\left(2^{n}-1\right)\\ & =3\cdot2^{n+1}-3-2^{n+1}+2\\ & =2\cdot2^{n+1}-1\\ & =2^{n+2}-1. \end{align*}