Why is n = 0 a valid basis for 1 + 2 + ... + n = (n^2 + n)/2?

The empty sum is 0 and (0+0)/2 = 0

Because the formula cannot be checked at n = 0

Because the sum for n = 0 equals 1

What algebra turns (k^2 + k)/2 + (k+1) into the target?

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

(k^2 + 2k)/2 = ((k+1)^2 + (k+1))/2

2072 Kartik

Induction: 1+2+...+n = (n²+n)/2

Short answer

Base n=0: empty sum 0. Assume 1+...+k = k(k+1)/2. Then sum to k+1 = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. This equals ((k+1)² + (k+1))/2, completing the induction.

Show by induction that for n ≥ 0, 1 + 2 + 3 + ... + n = (n² + n)/2.

Let P(n): 1 + 2 + 3 + ... + n = (n² + n)/2, for n ≥ 0 (the empty sum for n = 0 is 0).

Basis (n = 0)

LHS = 0 (empty sum). RHS = (0 + 0)/2 = 0. So P(0) is true. (Check n = 1: 1 = (1+1)/2 = 1.)

Induction hypothesis

Assume P(k) is true: 1 + 2 + ... + k = (k² + k)/2.

Induction step

Show that 1 + 2 + ... + k + (k+1) = ((k+1)² + (k+1))/2.

1 + 2 + ... + k + (k+1) = (k² + k)/2 + (k + 1)        (hypothesis)
                        = (k² + k + 2k + 2)/2
                        = (k² + 3k + 2)/2
                        = ((k² + 2k + 1) + (k + 1))/2
                        = ((k+1)² + (k+1))/2

This is exactly P(k+1).

Conclusion

By the principle of mathematical induction, 1 + 2 + ... + n = (n² + n)/2 for all n ≥ 0. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

All Theory of Computation chapter 1 questions →