2
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .