## 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=1k n = k(k + 1)/2

⇒ ∑n=1k n + (k + 1) = k(k + 1)/2 + (k + 1)

⇒ ∑n=1k+1 n = (k2 + k + 2k + 2)/2 = (k2 + 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:

12 + 22 + 32 + ... + n2 = 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=1k n2 = k(k + 1)(2k + 1)/6

⇒ ∑n=1k n2 + (k + 1)2 = k(k + 1)(2k + 1)/6 + (k + 1)2

⇒ ∑n=1k+1 n2 = k(2k2 + 3k + 1)/6 + k2 + 2k + 1

= (2k3 + 3k2 + k + 6k2 + 12k + 6)/6

= (2k3 + 9k2 + 13k + 6)/6

= (k + 1)(2k2 + 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:

13 + 23 + 33 + ... + n3 = [n2(n + 1)2]/4

Proof: By induction.

cactuspear home