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

Then, outline your proof.

- 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).