Proving recurrence by mathematical induction $f(1)=1,$
$f(n)=2f(n-1)+3$
($\forall n>1$)
has the following closed form solution 
$f(n)=2^{(n+1)}-3$
I understand that I can simply show that the recurrence is equal to $2^{(n+1)}-3$,but not with mathematical induction.
Any idea?
 A: hint: $f(n+1) = 2f(n)+3 = 2(2^{n+1}-3)+3=...$
A: Simply follow the standard steps used in mathematical induction. That is, you have a sequence $f(n)$ and you want to show that $f(n) = 2^{n+1} - 3$.


*

*Show that $f(n)=2^{n+1} - 3$ is true for $n=1$. This should be simple enough.

*Assume that $f(n)=2^{n+1} -3$ is true for some $n$. Then, show that, from this assumption, it follows that $$f(n+1) = 2^{(n+1) +1} -3.$$
To do that, you can use the fact that $f(n+1) = 2f(n) + 3$, and of course, you can use the induction hypothesis as well.

A: HINT:
Define $g(n) = f(n) + 3$, we will have
$$
g(n+1) = 2g(n)
$$
You then can solve $g(n)$ (it's a geometric progression), and thus $f(n)$.
A: If for some reason you are not too happy with straightforward induction, use difference equations. Put down the expression for $f(n-1)$: 
$$
f(n-1) = 2 f(n-2) + 3
$$
and subtract it from the one you have, then set $\Delta f(n) = f(n-1)-f(n)$. You get $\Delta f(n) = 2 \Delta f(n-1)$. Plug in the expression for $\Delta f(n-1)$ and so on until you reach $\Delta f(2)$. After this sum over $n$ on both sides. Note on the LHS you have a telescoping sum.   
