AI Tutor
If you want to prove a claim is true for every single integer from 11 to infinity, you cannot test them one by one. But what if you could build a mathematical chain reaction where every number automatically proves the next one?

The Domino Effect of Induction

In 1654, French mathematician Blaise Pascal formalized the Principle of Mathematical Induction to establish patterns across infinite rows of combinatorial numbers.
Induction works just like an infinite line of standing dominoes: if you push the first domino over, and every falling domino strikes the next one, every domino in the infinite chain must fall.
To construct a formal proof by induction, you must execute two distinct steps: the base case and the inductive step.
The base case verifies that the statement P(n)P(n) is true for the starting integer (usually n=1n = 1). The inductive step assumes P(k)P(k) is true for an arbitrary integer kk—known as the inductive hypothesis—and proves that P(k+1)P(k+1) must logically follow.
How do we apply this two-step machinery to formulas that add up long sequences of numbers?

Proving Summation Formulas

Let us prove that the sum of the first nn squares is given by the formula ∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} for all integers n≥1n \ge 1.
For the base case n=1n = 1, the left side is 12=11^2 = 1, and the right side evaluates to 1(1+1)(2(1)+1)6=66=1\frac{1(1+1)(2(1)+1)}{6} = \frac{6}{6} = 1, confirming the base case holds.
For the inductive step, assume the statement holds for n=kn = k: ∑i=1ki2=k(k+1)(2k+1)6\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}. We must deduce the formula for n=k+1n = k+1.