# Proving recurrence relations using induction

I'm trying to solve recurrence relations and then prove them via induction. I'm a bit stuck on this question. I'm finding it a bit hard to get it around my head for some reason. The recurrence relation is $$T(n) = 2 T(n/2) + 1$$

And the formula that I got for it is $$T(2^k) = 2^{k+1} -1$$

So for my induction, I did this:

Claim: $$T(2^k) = 2^{k+1} -1$$

Base case:

$$k = 1$$

$$T(2^1) - 1 = 2 - 1 = 1$$

Assuming that it's true for some $$k$$ so proving for $$k+1$$

Inductive case:

$$T(2^{k+1})$$

$$= 2 T(2^{k+1} /2) + 1$$

$$= 2 T(2^{k+1-1} ) + 1$$

$$= 2 T (2^k) + 1$$

$$= 2 T (2^{k+1} -1) + 1$$ (From the claim, -1 & +1 cancel out)

$$= 2 (2^{k+1} )$$

Could anyone tell me whether this would be the correct solution or if I've gone wrong somewhere? I'm a bit unsure on the last step, as I've got $$2x (2^k+1)$$ which is adding indices so maybe this would give $$2^k+2$$ which would be incorrect, but I'm unsure.

Thank you.

• Is the formula you got $2^{k+1}-1$? Commented Feb 18, 2020 at 0:53
• Or $2^k-1$? $\,2^k+1-1$ would be simply $2^k$ Commented Feb 18, 2020 at 1:00
• $2T(2^k)+1=2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1$ Commented Feb 18, 2020 at 1:06
• @J.W.Tanner yes sorry the formula should be $T(2^k) = 2^{k+1} -1$ Commented Feb 18, 2020 at 9:32
• Is it still wrong where you say “the formula that I got for it is”? Commented Feb 18, 2020 at 13:27

You showed that $$2T(2^{k+1})=2T(2^k)+1$$.

From the inductive hypothesis, this is $$2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1$$, as desired.