# Easy Induction Problem 1

### General-purpose hint

Have you looked at the simpler examples at the start of the induction chapter in the book? Induction proofs of simple numerical formulas tend to be quite similar to one another. Perhaps you could use one of those proofs as a model and adapt it to solve this problem?

### Hints: Getting started

Notice that the induction variable must be n, because it's the only integer variable in the problem.

Identify the induction variable n and the claim P(n). P(n) must be a statement that could be true or false. P(n) cannot be an expression returning a number. So, for example, $$\frac{x^{n+1}-1}{x-1}$$ cannot be P(n).

• Base case
• Inductive hypothesis
• Goal to reach at the end of the inductive step

For your base case, identify the smallest integer for which the claim is supposed to work and substitute that in for n. Does the claim work?

If your claim is true for integers starting with p, then your inductive hypothesis should look like "Suppose P(n) is true for n=p,...k". The goal to reach at the end of the inductive step will be P(k+1).

Your inductive hypothesis tells you that "P(n) is true for n=p,...k". In particular, you know that P(k) is true. Perhaps you should write out what P(k) is?

Actually write out what P(k+1) is. This will mean substituting n=k+1 in the formula you are trying to prove.

### Hints: The algebra

You need to use the equation P(k) to prove the equation P(k+1). Two hints about organizing your work.

First, compare the left side of P(k) to the left side of P(k+1). Similarly the right sides. How are they the same? How exactly do they differ? When comparing the two summations, write the longer summation as the shorter summation plus an extra term.

Second, a good way to prove a numerical equality is to start with the lefthand side and work gradually towards the righthand side. So start with the lefthand side of P(k+1) and try to work towards the righthand side of P(k+1).