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

-

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

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

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!

-

You have to choose a(1). You can open the formula for n=2,...,n. You get in this way n-1 equalities. The product of all the left members of those equalities is equal to the product of all right members. You can simplify in both products a(2) ....a(n-1). Then you get that a(n)=2^n-1 * a(1)

Sorry, I did not see the +1 , so my answer was for a(n)=2a(n-1) But with the next answer it can help a little (-:.

-