1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The book has not made a mistake: wolframalpha.com/input/… $\endgroup$ – parsiad Apr 6 '16 at 20:37
  • $\begingroup$ 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$. $\endgroup$ – lulu Apr 6 '16 at 20:39
  • $\begingroup$ $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. $\endgroup$ – JMoravitz Apr 6 '16 at 20:39
1
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.