## 2.3. The Principle of Induction

### Example 2.3.12: Sum of Squares and Cubes

- The sum of the first
*n*numbers is equal to - The sum of the first
*n*square numbers is equal to - 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:

Each column except the last adds up to

1 + 2 + 3 + ... + (n-1) + n = S n + (n-1) + (n-2) + ... + 2 + 1 = S

*n+1*, and there are

*n*of them. The last column adds up to

*2 S*, so that we have the equation:

from which the result follows.n (n+1) = 2 S

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

Property *Q(n)*:

Check1 + 2^{2}+ 3^{2}+ ... + n^{2}=

*Q(1)*:

which is true. Now assume1 = 1 × 2 × 3 / 6 = 1

*Q(n)*is true, let's prove

*Q(n+1)*:

The last expression is exactly property Q(n+1), which finishes the induction proof.1 + 2^{2}+ 3^{2}+ ... + n^{2}+ (n+1)^{2}=

= + (n+1)^{2}=

= =

= =

=

**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 n ^{2} + 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.