## some properties of the natural numbers

### sum of integers

The sum of the first n natural numbers is given by:

1 + 2 + 3 + ... + n = n(n + 1)/2

Proof: By induction, let P(k) be the proposition that the above relation holds for the integer k. With k = 1, we have 1 = 1(1 + 1)/2, so P(1) is true.

Next, assume P(k). That is, that ∑_{n=1}^{k} n = k(k + 1)/2

⇒ ∑_{n=1}^{k} n + (k + 1) = k(k + 1)/2 + (k + 1)

⇒ ∑_{n=1}^{k+1} n = (k^{2} + k + 2k + 2)/2 = (k^{2} + 3k + 2)/2 = (k + 1)(k + 2)/2

We have shown P(k + 1).

QED

Note: The above sum is equal to C(n + 1, 2). That is, the sum of the first n numbers is equal to the number of unordered pairs chosen from n + 1 objects. To see why this is true, imagine a bowl with k + 1 candies, each a different color. How many different ways are there to choose two candies from the bowl? There are k pairings involving the first color chosen, k − 1 pairings involving the second, because we have already counted the pair consisting of the first color and the second color, and so on.

### sum of squares

The sum of the squares of the first n natural numbers:

1^{2} + 2^{2} + 3^{2} + ... + n^{2} = n(n + 1)(2n + 1)/6

Proof: By induction, let Q(k) be the proposition that the above relation holds for the integer k. With k = 1, we have 1 = 1(1 + 1)(2 + 1)/6, so Q(1) is true.

Next, assume Q(k). That is, that ∑_{n=1}^{k} n^{2} = k(k + 1)(2k + 1)/6

⇒ ∑_{n=1}^{k} n^{2} + (k + 1)^{2} = k(k + 1)(2k + 1)/6 + (k + 1)^{2}

⇒ ∑_{n=1}^{k+1} n^{2} = k(2k^{2} + 3k + 1)/6 + k^{2} + 2k + 1

= (2k^{3} + 3k^{2} + k + 6k^{2} + 12k + 6)/6

= (2k^{3} + 9k^{2} + 13k + 6)/6

= (k + 1)(2k^{2} + 7k + 6)/6

= (k + 1)(k + 2)(2k + 3)/6

We have shown Q(k + 1).

QED

### sum of cubes

The sum of the cubes of the first n natural numbers:

1^{3} + 2^{3} + 3^{3} + ... + n^{3} = [n^{2}(n + 1)^{2}]/4

Proof: By induction.