0
$\begingroup$

Possible Duplicate:
Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

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.

  • 2
    See [this answer](http://math.stackexchange.com/a/106061/12042) for three ways to solve exactly this recurrence.2012-04-09

2 Answers 2

2

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!

1

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 (-:.