I am working through some of the problems in the appendix of my algorithms book...
They are showing thatis
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 asor
What I don't get isI see that I can distribute the
to get the previous result. But Why do we want this form?
Is it because I want to expressin a way that I can make it comparable to
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.
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).
  |
LinkBack URL
About LinkBacks