# solve recurrence relation $a(n)=2a(n-1)+1$ [duplicate]

I am trying to solve following recurrence relation

$$a(n)=2a(n-1)+1\;.$$

I have divided both side by $2^n$, so get $$a(n)2^{-n}=2^{1-n}a(n-1)+2^{-n}\;.$$

After I put $n=1$ I have got $a(1)=2a(0)$, so $a(0)=1/2$, but how to continue for the general solution? I can't use formula of quadratic equation, namely $k^2-2k-1=0$, because in this case $k_1=1+\sqrt2$ and $k_2=1-\sqrt2$, but it does not help me to find actual solution.

-
See this answer for three ways to solve exactly this recurrence. –  Brian M. Scott Apr 9 '12 at 8:19

## marked as duplicate by Brian M. Scott, t.b., Martin Sleziak, Asaf Karagila, lhfApr 9 '12 at 11:01

You can't deduce $a(0)$ from your recurrence.

Add $1$ on both sides to get $$b(n)=a(n)+1=2(a(n-1)+1)$$ so that $$b(n)=2 b(n-1)$$

Fine continuation!

-