Need help understanding a proof by induction

Printable View

September 25th 2012, 06:27 PM
restin84

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 $\sum_{k=0}^{n}3^k$ is $O(3^n)$ or $\sum_{k=0}^{\n}3^k <= c3^n$ 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

$\sum_{k=0}^{n+1}3^k = \sum_{k=0}^{n}3^k +3^{n+1} <= c3^n + 3^{n+1} = (\frac{1}{3} + \frac{1}{c})c3^{n+1} <= c3^{n+1}$
as long as $(\frac{1}{3} + \frac{1}{c}) <= 1$ or $c>=3/2$

What I don't get is $(\frac{1}{3} + \frac{1}{c})c3^{n+1}$ I see that I can distribute the $c3^{n+1}$ to get the previous result. But Why do we want this form?
Is it because I want to express $c3^n + 3^{n+1}$ in a way that I can make it comparable to $c3^{n+1}$ ?
September 25th 2012, 08:29 PM
chiro

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.
September 25th 2012, 08:48 PM
johnsomeone

Re: Need help understanding a proof by induction

During the induction, you've gotten to here:

$\sum_{k=0}^{n+1}3^k \le c3^n + 3^{n+1}$ ,

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 $\sum_{k=0}^{n+1}3^k \le c3^{n+1}$ .

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: $\sum_{k=0}^{n+1}3^k \le c3^n + 3^{n+1}$ ,

and you want to show that that implies this: $\sum_{k=0}^{n+1}3^k \le c3^{n+1}$ .

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