Proving recurrence by mathematical induction

Question

$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?

Answer 1

hint: $f(n+1) = 2f(n)+3 = 2(2^{n+1}-3)+3=...$

Answer 2

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$.

1. Show that $f(n)=2^{n+1} - 3$ is true for $n=1$. This should be simple enough.
2. 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.

Answer 3

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.

Answer 4

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)$.