Need help understanding a proof by induction

I am working through some of the problems in the appendix of my algorithms book...

They are showing that is or for some constant c

The initial condition was shown to be true as long as c >= 1. They assume that the bound holds for n and then show that it holds for n+1

as long as or

What I don't get is I see that I can distribute the to get the previous result. But Why do we want this form?

Is it because I want to express in a way that I can make it comparable to ?

Re: Need help understanding a proof by induction

Hey restin84.

The basic reason is to prove that there exists some finite constant real number c that satisfies the identity: what that constant is is not of too much concern. The concern is that the constant actually exists and is a finite real number.

Remember that you are looking for a final constant c that exists not any of the intermediate c's used in the induction step.

Re: Need help understanding a proof by induction

During the induction, you've gotten to here:

,

but, in order to complete the induction, you're SEEKING to be able to write this:

"And so, assuming it's true for all values up to n, have shown that it follows that .

Therefore, it being true up to n implies it's true up to n+1, and since it was shown true for n=1, this proves, by induction, that it's true for all n."

----

So you have this: ,

and you want to show that that implies this: .

Well, you do the algebraic manipulation that you wrote there to show that the first situation implies the second situation (when c >=3/2).