Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
See this answer for three ways to solve exactly this recurrence. –  Brian M. Scott Apr 9 '12 at 8:19
add comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

up vote 2 down vote accepted

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!

share|improve this answer
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.