---
title: "Induction: 1+2+...+n = (n²+n)/2"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:induction-sum-natural"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-sum-natural
site: BCT Engineering
---

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

Theory of Computation · Chapter 1: Introduction

- Asked in: 2072 Kartik
- Video: [Proof by Mathematical Induction - How to do a Mathematical Induction Proof ( Example 1 )](https://www.youtube.com/watch?v=dMn5w4_ztSw) — Learn Math Tutorials
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-sum-natural
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Show by induction that for n ≥ 0, 1 + 2 + 3 + ... + 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.

## Answer

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.

```text
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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Why is n = 0 a valid basis for 1 + 2 + ... + n = (n^2 + n)/2?
   A. Because the formula cannot be checked at n = 0
   B. The empty sum is 0 and (0+0)/2 = 0
   C. Because 1 = (1+1)/2 holds
   D. Because the sum for n = 0 equals 1
   Answer: B. The claim is for n ≥ 0, and the empty sum equals 0, matching the formula. (Key point: Basis)

2. In the step, what is added to the hypothesis value (k^2 + k)/2?
   A. The term (k+1)^2
   B. The term k
   C. The term (k^2 + k)
   D. The new term (k + 1)
   Answer: D. The sum up to k+1 equals the sum up to k plus the next term k + 1. (Key point: Step setup)

3. What algebra turns (k^2 + k)/2 + (k+1) into the target?
   A. (k^2 + 3k)/2 = (k+1)(k+2)/4
   B. (k^2 + k + 1)/2 = ((k+1)^2)/2
   C. (k^2 + 3k + 2)/2 = ((k+1)^2 + (k+1))/2
   D. (k^2 + 2k)/2 = ((k+1)^2 + (k+1))/2
   Answer: C. Writing k^2 + 3k + 2 = (k^2 + 2k + 1) + (k + 1) gives exactly P(k+1). (Key point: Algebra)