Solve the recurrence: t(n) = t(n/2) + n + 2 (Solution included).

[s3a]

Homework Statement

The problem along with its solution is attached as Problem.jpg.

Homework Equations

Recurrence relation.

The Attempt at a Solution

I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n) because n = 2^k = 2^(log2(n)) = n.

I would greatly appreciate it if someone could help me get unstuck!
Thanks in advance!

 

[RoshanBBQ]

Homework Statement

The problem along with its solution is attached as Problem.jpg.

Homework Equations

Recurrence relation.

The Attempt at a Solution

I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n) because n = 2^k = 2^(log2(n)) = n.

I would greatly appreciate it if someone could help me get unstuck!
Thanks in advance!

You forgot to attach Problem.jpg.

 

[s3a]

Lol. Thanks for telling me.

 

[NascentOxygen]

Seems there is a "+" sign missing in (4).

It should be t(n/2^k) +[/color] n + n/2 + ...

Then in going from (5) to (6), make use of the fact that
n/2^k-1 ≡ n/(2^k/2)
   ≡ 2n/2^k, but k=log₂n
   ≡ 2n/n
   ≡ 2