## Saturday, October 24, 2009

### Proofs of Arithmetic Progression

Challenge:

Find as many proofs of the arithmetic progression; i.e. prove 1 + 2 + 3 + 4 + ... + n = 0.5 * n * (n + 1)

I have thought of four proofs, as detailed below.

Proof 1: Proof by Pairing

We pair the first and last elements, then the second first and second last elements, and so on. Each pair will have the same sum, since the earlier element gains 1 while the later element loses 1. Now, divide any pair by half. If there are even number of elements, all elements will be paired, and since each pair is the same, the average is found by diving any pair by half. Now, if there are odd number of elements, the remaining element, lying in the center of the sequence, will have the same value as the half of any pair, and this also yields the average.

Having the average, the sum can be found by simply multiplying by the number of elements, which is n. Hence,

Sum = 0.5 * (first element + last element) * (number of elements)
==> Sum = 0.5 * (n + 1) * (n)

Proof 2: Proof by Mathematical Induction

Suppose that the sum for a sequence (1 + 2 + ... + n) is equal to 0.5 * n * (n + 1) for some value of n = k.

Then, for the sum of a sequence (1 + 2 + ... + (k +1)), we have:
Sum = (1 + 2 + ... + k) + (k + 1)
==> Sum = 0.5 * k * (k + 1) + (k + 1)
==> Sum = 0.5 * (k + 2) * (k + 1)
Hence, if the identity is valid for n = k, it is also valid for n = k+1.

Now, consider n = 1.
Sum = 0.5 * (1) * (1+1) = 1.
Hence, it is true for n=1 ==> true for all n.

Proof 3: Proof by Square

Consider the following image. A (n+1) by (n+1) square can be broken up into three pieces; n + 1 unit squares, and two arithmetic progressions of (1 + 2 + ... + n). Using this relation,

(n + 1) ^ 2 = (n + 1) + 2 * Sum
==> Sum = 0.5 * ((n + 1) * (n + 1) - (n + 1))
==> Sum = 0.5 * (n) * (n + 1)

Proof 4: Proof by Triangle

Consider the following image. A triangle of base (n+1) and height (n+1) can be obtained from an arithmetic sequence of of (1 + 2 + ... + n) by adding n + 1 triangles of 0.5 unit area. Using this idea,

Sum = o.5 * (n + 1) * (n + 1) - 0.5 * (n + 1)
==> Sum = 0.5 * (n) * (n + 1)

I hope that you have found this exercise to be entertaining.