# Interactive Real Analysis

Next | Previous | Glossary | Map

## 2.3. The Principle of Induction

### Example 2.3.12: Sum of Squares and Cubes

Prove the following statements via induction:
1. The sum of the first n numbers is equal to
2. The sum of the first n square numbers is equal to
3. The sum of the first n cubic numbers is equal to
1. We actually have already proved this statement in example 2.3.4, but we should mention another proof of this statement that does not use induction.

Actually, as the story goes, the young Gauss, who later became a famous mathematician, was once in grade school. His teacher, who did not want to teach anything, asked his students to compute the sum of the first 100 integers, thinking that this would give him plenty of time to read a newspaper. However, after a few seconds the young Gauss came up with the correct answer, much to the dismay of his teacher.

How was Gauss able to find the answer so quickly ? He certainly did not know about induction, so he used the following trick. We want to find 1 + 2 + 3 + ... + n-1 + n. Instead of finding that sum once, we compute it twice, calling the unknown answer S. We list the numbers once in forward and once in backward order:

 1 + 2 + 3 + ... + (n-1) + n = S n + (n-1) + (n-2) + ... + 2 + 1 = S
Each column except the last adds up to n+1, and there are n of them. The last column adds up to 2 S, so that we have the equation:
n (n+1) = 2 S
from which the result follows.

2. Let's prove the second statement via induction.

Property Q(n):

1 + 22 + 32 + ... + n2 =
Check Q(1):
1 = 1 × 2 × 3 / 6 = 1
which is true. Now assume Q(n) is true, let's prove Q(n+1):
1 + 22 + 32 + ... + n2 + (n+1)2 =
= + (n+1)2 =
= =
= =
=
The last expression is exactly property Q(n+1), which finishes the induction proof.

3. We will - of course - leave the third statement as an exercise. It may be that the last step requires some factorization that may or may not be easy to do. Instead, try working your way 'backward'. For example, instead of trying to factor an expression such as 2 n2 + 7n + 6, you could start with the answer you are hoping to get, in this case (n + 2)(2n + 3), and work your way back.

Next | Previous | Glossary | Map