Solve recurrence relation: $P_1=1; P_n=P_{n-1}+2^n\\$
I am completely new in this type of equations. Can somebody explain this to me? I tried myself and got something like this:
$P_n=1+1/2+1/2^2+1/2^3+...+2^n$
And I don't know if this is correct and how to continue
For the homogenous solution $P_{n}-P_{n-1}=0$ you try a solution of the form $P_{n}=x^{n}$. So substituting gives $$x^{n}-x^{n-1}=x^{n-1}(x-1)=0$$
So $x=0,1$ and the homogenous solution is $P_{n}=C_{1}$.
Next we want to find a particular solution of the full recurrence $$P_{n}-P_{n-1}=2^n.$$
So we look for a solution of the form $P_{n}=k2^{n}$, for some constant $k$. So substituting into the equation gives
$$k2^{n}-k2^{n-1}=k2^{n-1}(2-1)=k2^{n-1}=2^{n}$$
Now diving both sides by $2^{n-1}$ we obtain that $k=2.$
Thus we have the solution $P_{n}=C_{1}+2^{n+1}.$
Now since we know that $P_{1}=1$ then $P_{1}=C_{1}+2^{2}=C_{1}+4=1$ so $C_{1}=-3$. Hence the general solution is $$P_{n}=2^{n+1}-3.$$
Iteration method.
We have $P_{n-1}=P_{n-2}+2^{n-1}$ so $P_{n}=P_{n-1}+2^{n}=P_{n-2}+2^{n-1}+2^{n}.$
Then $P_{n-2}=P_{n-3}+2^{n-2}$ which gives
$P_{n}=P_{n-2}+2^{n-1}+2^{n}=P_{n-3}+2^{n-2}+2^{n-1}+2^{n}$
Thus $P_{n}=P_{n-k}+2^{n-(k-1)}+2^{n-(k-2)}+...+2^{n-1}+2^{n}$
So when $n-k=1$ we have $P_{n}=P_{1}+2^{(n-k)+1}+2^{(n-k)+2}+...+2^{n-1}+2^{n}=1+2^{2}+2^{3}+....+2^{n-1}+2^n$
$=1+2^{2}(1+2+2^{2}+...+2^{n-3}+2^{n-2})$.
Now we will use that the sum of the first $n+1$ terms of a geometric series is $$\sum_{k=0}^{n}ar^{k}=a(\frac{r^{n+1}-1}{r-1})$$
Thus we obtain $$P_{n}=1+2^{2}(1+2+2^{2}+...+2^{n-3}+2^{n-2})$$ $$1+2^{2}\sum_{k=0}^{n-2}2^k=1+2^{2}\frac{2^{n-1}-1}{2-1}$$ $$=1+2^2(2^{n-1}-1)=1+2^{n-1+2}-2^{2}=2^{n+1}-3$$ as required.
