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² + k + 2k + 2)/2 = (k² + 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² + 3² + ... + n² = 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² = k(k + 1)(2k + 1)/6

⇒ ∑_n=1^k n² + (k + 1)² = k(k + 1)(2k + 1)/6 + (k + 1)²

⇒ ∑_n=1^k+1 n² = k(2k² + 3k + 1)/6 + k² + 2k + 1

= (2k³ + 3k² + k + 6k² + 12k + 6)/6

= (2k³ + 9k² + 13k + 6)/6

= (k + 1)(2k² + 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³ + 2³ + 3³ + ... + n³ = [n²(n + 1)²]/4

Proof: By induction.