# Easy Induction Problem 1

### Solution

Base case: For n=0, we have $$\sum_{i=0}^n x^i =x^0=1$$ and $$\frac{x^{n+1}-1}{x-1} = \frac{x^{0+1}-1}{x-1} = \frac{ x-1}{x-1} = 1$$. So $$\sum_{i=0}^n x^i =\frac{x^{n+1}-1}{x-1}$$.

Inductive hypothesis: Suppose $$\sum_{i=0}^n x^i =\frac{x^{n+1}-1}{x-1}$$ for n=0,1,...,k.

Rest of inductive Step: We know that $$\sum_{i=0}^{k+1} x^i = x^{k+1} + \sum_{i=0}^k x^i$$.

By the inductive hypothesis, $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$.

So $$\sum_{i=0}^{k+1} x^i = x^{k+1} + \sum_{i=0}^k x^i = x^{k+1} + \frac{x^{k+1}-1}{x-1} = \frac{(x-1)x^{k+1}}{x-1} + \frac{x^{k+1}-1}{x-1} = \frac{x^{k+2}-x^{k+1}}{x-1} + \frac{x^{k+1}-1}{x-1} = \frac{x^{k+2}-x^{k+1}+ x^{k+1}-1}{x-1} = \frac{x^{k+2}-1}{x-1}$$.

Therefore $$\sum_{i=0}^{k+1} x^i = \frac{x^{k+2}-1}{x-1}$$, which is what we needed to show.

The main parts of the inductive proof are labeled. Authors writing for advanced classes sometimes omit the labels. However the labels are very important when you are learning to write these proofs.

For the base case, we need to check that $$\sum_{i=0}^n x^i =\frac{x^{n+1}-1}{x-1}$$ by showing that both sides equal 1. Don't write things like $$\sum_{i=0}^n x^i =\frac{x^{n+1}-1}{x-1} = 1$$ which suggest that you already know they are equal before you figure out what they are equal to.

The inductive hypothesis contains three different variables. i is the moving variable for the summation (local to the lefthand side of the equation). n is the moving variable for the induction. And k is the bound, i.e. the largest value of n for which you assume the claim is true. If you have only two variables, something has gone wrong.

Does your inductive hypothesis look like this?

Suppose $$\sum_{i=0}^k x^i =\frac{x^{k+1}-1}{x-1}$$

That is a so-called "weak" inductive hypothesis. For this problem, it's ok mathematically and this form would be ok in some other math classes. However, for this class, you must write all your inductive hypotheses as "strong" i.e. true for all values up through k. Many inductive proofs in computer science require strong hypotheses. We want you to practice writing them.

Check the bound of your inductive hypothesis (k in the above proof) and the bound in the conclusion of your inductive step (k+1 above). There should be a jump of exactly 1 between the two values. So it's ok to assume the claim is true up through k-1 and prove it's true for k. However, it's not ok to assume the claim is true through k-1 and prove it's true for k+1. Also not ok to assume the claim is true for values up to k+1 and show it's true at n=k.

Somewhere in your inductive step, you should use the inductive hypothesis. It's not critical that you said "by the inductive hypothesis" explicitly. But you should be able to point at the place where you used it in your algebra. If you can't do that, even after reading through this solution, go to office hours to get help.