## Example 2.3.12: Sum of Squares and Cubes |

Prove the following statements via 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

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}=

which is true. Now assume1 = 1 × 2 × 3 / 6 = 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