# Thread: Need help understanding a proof by induction

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

$\displaystyle \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 $\displaystyle (\frac{1}{3} + \frac{1}{c}) <= 1$ or $\displaystyle c>=3/2$

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

2. ## 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.

3. ## Re: Need help understanding a proof by induction

During the induction, you've gotten to here:

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

and you want to show that that implies this: $\displaystyle \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).