Sum of the First n Positive Integers

Prove that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for every $n \ge 1$.

Base case: check $n = 1$: Left side: $1$. Right side: $\dfrac{1 \cdot 2}{2} = 1$ = $P(1)$ is true

Inductive hypothesis: assume $P(k)$ for some $k \ge 1$: Assume $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ = We may use this equation

Inductive step: add the next term $k+1$ to both sides: $1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ = $= \dfrac{(k+1)(k+2)}{2}$

Compare with $P(k+1)$: $P(k+1)$ says the sum equals $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ = $P(k+1)$ is true

Answer: By induction, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ for every $n \ge 1$. For example, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$.

Sum of the First n Odd Numbers

Prove that $1 + 3 + 5 + \dots + (2n-1) = n^2$ for every $n \ge 1$.

Base case: check $n = 1$: Left side: $1$. Right side: $1^2 = 1$ = $P(1)$ is true

Inductive hypothesis: Assume $1 + 3 + \dots + (2k-1) = k^2$ for some $k \ge 1$ = We may use this equation

Find the next odd number: The odd number after $2k-1$ is $2(k+1) - 1 = 2k + 1$ = Add $2k + 1$

Inductive step: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, so $P(k+1)$ is true

Answer: By induction, the sum of the first $n$ odd numbers is $n^2$. Check: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Sum of Powers of 2

Prove that $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ for every $n \ge 0$.

Base case: here the first value is $n = 0$: Left side: $2^0 = 1$. Right side: $2^{1} - 1 = 1$ = $P(0)$ is true

Inductive hypothesis: Assume $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ for some $k \ge 0$ = We may use this equation

Inductive step: add the next term $2^{k+1}$: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Simplify and compare with $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ is true

Answer: By induction, $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ for every $n \ge 0$. Check for $n = 6$: $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

A Divisibility Proof

Prove that $n^3 - n$ is divisible by $3$ for every $n \ge 1$. (The Direct Proof lesson showed this by factoring; now we use induction.)

Base case: check $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ is true

Inductive hypothesis: Assume $k^3 - k = 3m$ for some integer $m$ = $k^3 - k$ is a multiple of $3$

Expand the expression for $k+1$: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Use the hypothesis: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Conclude: $m + k^2 + k$ is an integer, so the expression is a multiple of $3$ = $P(k+1)$ is true

Answer: By induction, $3$ divides $n^3 - n$ for every $n \ge 1$. Check for $n = 5$: $125 - 5 = 120 = 3 \cdot 40$.

An Inequality: 2 to the n Is Greater Than n

Prove that $2^n > n$ for every $n \ge 1$.

Base case: check $n = 1$: $2^1 = 2$ and $2 > 1$ = $P(1)$ is true

Inductive hypothesis: Assume $2^k > k$ for some $k \ge 1$ = We may use this inequality

Write $2^{k+1}$ using $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Compare $2k$ with $k+1$: $2k = k + k \ge k + 1$, because $k \ge 1$ = $2k \ge k + 1$

Chain the inequalities: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, so $P(k+1)$ is true

Answer: By induction, $2^n > n$ for every $n \ge 1$. For example, $2^{10} = 1024 > 10$.

Mistake: Skipping the base case

Why: The inductive step alone proves nothing: it only says IF one domino falls, the next one falls too. Example: the false claim $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ has a working inductive step, but for $n = 1$ the left side is $1$ and the right side is $2$.

Correct: Always check the first case explicitly. Without a first falling domino, nothing falls.

Mistake: Assuming what you want to prove

Why: Writing "assume $P(n)$ is true for all $n$" or "assume $P(k+1)$" is circular: it assumes the conclusion.

Correct: Assume $P(k)$ for ONE value $k$ (the inductive hypothesis) and prove $P(k+1)$ from it.

Mistake: Wrong algebra in the inductive step

Why: A common slip is adding the wrong next term, for example adding $2k - 1$ instead of $2k + 1$ in the odd number sum, or forgetting to add the new term on one side.

Correct: Write out $P(k+1)$ in full first (replace every $n$ by $k+1$), then work toward exactly that expression.

Mistake: Thinking that checking many cases is a proof

Why: The formula $n^2 + n + 41$ gives prime numbers for $n = 0, 1, \dots, 39$, but for $n = 40$ it gives $1681 = 41^2$, which is not prime.

Correct: Examples help you guess a formula. Only the base case plus the inductive step proves it for every $n$.

Checking Computer Programs

Programmers use induction to prove that a loop gives the right answer after any number of rounds: if it is correct after $k$ rounds, it is correct after $k+1$ rounds.

A loop adds $1, 2, 3, \dots$ to a running total. Induction proves that after $n$ rounds the total is $\dfrac{n(n+1)}{2}$.

The Tower of Hanoi

In this puzzle you move a stack of discs to another peg, one disc at a time, never putting a larger disc on a smaller one. Induction proves that $n$ discs need $2^n - 1$ moves.

To move $k+1$ discs, move the top $k$ discs away, move the largest disc, then move the $k$ discs back on top: $2(2^k - 1) + 1 = 2^{k+1} - 1$ moves.

Rice on a Chessboard

An old legend: put $1$ grain of rice on the first square, $2$ on the second, $4$ on the third, doubling each time. The sum of powers of 2 tells you the total.

On the first $3$ squares there are $1 + 2 + 4 = 7 = 2^3 - 1$ grains.

Q: Why does induction really prove the statement for ALL n?

A: The base case gives $P(1)$. The step with $k = 1$ gives $P(2)$, with $k = 2$ gives $P(3)$, and so on. Every positive integer is reached after finitely many steps, so no $n$ is left out.

Q: Does the base case always have to be n = 1?

A: No. Start at the first value from which the statement should hold. The sum of powers of 2 starts at $n = 0$. The statement $2^n > n^2$ fails for $n = 2, 3, 4$ (for example $2^4 = 16 = 4^2$) and holds for every $n \ge 5$, so that proof uses the base case $n = 5$.

Q: Is mathematical induction the same as inductive reasoning in science?

A: No. Inductive reasoning guesses a general rule from examples and can be wrong. Mathematical induction is a deductive proof: once the base case and the step are proven, the result is certain.

Q: What is strong induction?

A: In strong induction the hypothesis assumes $P(1), P(2), \dots, P(k)$ are all true, not only $P(k)$. It is useful when $P(k+1)$ depends on several earlier cases, for example in proofs about prime factorizations.