PROOF 28

Prove.

1 + 2 + … + n = n(n+1)/2

On the natural numbers ℕ.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

S(n) is the sum from 1 to n, defined by S(1) = 1, S(k+1) = S(k) + (k+1).

Proof.

These two equations determine S(n) uniquely for each natural number n.convention

∎

Definition D2

a ÷ b means the x satisfying b × x = a.

Proof.

a ÷ b has a value only when such an x is unique.convention

∎

Lemma L1

Let P(n) be “2S(n) = n(n+1)”. Then P(1) holds.

Proof.

(1)S(1) = 1D1

(2)2S(1) = 2 × 1 = 2(1), E, A5

(3)1 + 1 = 2A6

(4)1(1+1) = 1 × 2 = 2 × 1 = 2(3), A4, A5

(5)2S(1) = 1(1+1)(2), (4)

∎

Lemma L2

For every natural number k, if P(k), then P(k+1).

Proof.

(1)Suppose 2S(k) = k(k+1).assumption

(2)S(k+1) = S(k) + (k+1)D1

(3)2S(k+1) = 2(S(k) + (k+1))(2), E

(4)　　　　 = 2S(k) + 2(k+1)(3), A3

(5)　　　　 = k(k+1) + 2(k+1)(4), (1)

(6)k(k+1) = (k+1)k, 2(k+1) = (k+1)2A4

(7)(k+1)k + (k+1)2 = (k+1)(k+2)A3

(8)k + 2 = k + (1+1) = (k+1) + 1A6, A2

(9)2S(k+1) = (k+1)((k+1)+1), so P(k+1) holds.(5), (6), (7), (8)

∎

Theorem T1

For every natural number n, 2S(n) = n(n+1)

Proof.

(1)P(1) holds.L1

(2)For every k, P(k) ⟹ P(k+1).L2

(3)Therefore P(n) holds for every n.(1), (2), A1

∎

Corollary C

For every natural number n, 1 + 2 + … + n = n(n+1)/2

Proof.

(1)2S(n) = n(n+1)T1

(2)n(n+1) ÷ 2 is the x with 2x = n(n+1).D2

(3)S(n) is such an x.(1), (2)

(4)If 2x = 2y then x = y, so such an x is unique.A7

(5)S(n) = n(n+1)/2(3), (4), D2

∎

Remark

Can A1 be removed from this proof?

The body of the proof is just the two lines L1 and L2. Check how far those two lines reach when it is removed.