Proving Fibonacci recursive algorithm time complexity

I am trying to understand a proof by induction in my algorithms text book. Here's the author is proving using induction that the T(n) will always be greater than 2^(n/2) (This is for calculating the nth fibonacci number using the recursive algorithm):

Wha开发者_如何转开发t I don't understand is the very last step, where he is manipulating the equation. How does he go from:

> 2^(n-1)/2 + 2^(n-2)/2 +1

to

> 2^(n-2)/2 + 2^(n-2)/2 +1

He just randomly changes 2^(n-1)/2 to 2^(n-2)/2. Is this a mistake?

Thanks.

It's deliberate, if you look closely it's an inequation and he uses it do finish the induction step.

Note the typo, it should say "We must show that T(n) > 2^(n/2)" and not <.

I believe that particular step runs off the assumption that:

T(n-1) > T(n-2)

Therefore, we can form an algebraic inequality:

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2) + 1

We can lop off the + 1 from the right side (because the inequality will still hold true for anything subtracted away on the LESSER side):

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2)

From this, substitute our T(m) = 2^(m/2) (for anything less than n and > 2, which n-1 and n-2 both qualify):

2^(n-1)/2 + 2^(n-2)/2 + 1 > 2^(n-2)/2 + 2^(n-2)/2

That gets you that particular step. It's done this way deliberately as the poster above me stated, to get to 2^(n/2).