Problem-Solving StrategyDifficulty 30-95774 tagged problems

Mathematical Induction

Mathematical Induction is the habit of proving infinitely many statements by establishing a base case and a reliable step. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$P(1)\text{ true}\quad\text{and}\quad \big(P(k)\Rightarrow P(k+1)\big)\ \forall k \;\;\Longrightarrow\;\; P(n)\ \text{true } \forall n \ge 1.$$

Prove a statement for the first case, then prove that whenever it holds for one case it holds for the next, and it follows for all cases at once — like toppling an infinite line of dominoes.

Why It Works

1
Base case: verify $P(1)$ directly.
2
Inductive hypothesis: assume $P(k)$ is true for an arbitrary fixed $k \ge 1$.
3
Inductive step: using that assumption, prove $P(k+1)$.
4
Since $P(1)$ holds and each true case forces the next, every $P(n)$ holds: the dominoes fall from $1$ onward without gap.

Worked Examples

Example 1

Prove that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for every positive integer $n$.

1
Base case $n=1$: the left side is $1$ and the right side is $\frac{1\cdot 2}{2} = 1$, so $P(1)$ holds.
2
Assume $P(k)$: $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$.
3
Add $k+1$ to both sides: $1 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$.
4
That is exactly $P(k+1)$, so by induction the formula holds for all $n \ge 1$.

Answer:

$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \ge 1$.

Contest level

Prove that $n^3 - n$ is divisible by $6$ for every positive integer $n$.

1
Base case $n = 1$: $1^3 - 1 = 0$, and $6 \mid 0$, so $P(1)$ holds.
2
Assume $P(k)$: $6 \mid k^3 - k$.
3
Expand the next case: $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1)$.
4
The first term is divisible by $6$ by hypothesis; $k(k+1)$ is a product of two consecutive integers, hence even, so $3k(k+1)$ is divisible by $6$. Their sum is divisible by $6$, giving $P(k+1)$.

Answer:

$6 \mid n^3 - n$ for all $n \ge 1$.

Olympiad / Challenge

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

1
Base case $n = 5$: $2^5 = 32 > 25 = 5^2$, so the claim holds at the starting value. (Note it fails at $n = 4$, where $2^4 = 4^2 = 16$, so $n = 5$ is the right base.)
2
Assume $2^k > k^2$ for some $k \ge 5$.
3
Then $2^{k+1} = 2 \cdot 2^k > 2k^2$. It remains to show $2k^2 \ge (k+1)^2$.
4
Since $2k^2 - (k+1)^2 = k^2 - 2k - 1 = (k-1)^2 - 2 \ge (5-1)^2 - 2 = 14 > 0$ for $k \ge 5$, we get $2^{k+1} > 2k^2 \ge (k+1)^2$, which is $P(k+1)$.

Answer:

$2^n > n^2$ for all $n \ge 5$.

Going Deeper

Induction proves far more than summation formulas: divisibility ($6 \mid n^3 - n$), inequalities ($2^n > n^2$), and structural claims about trees, graphs, and tilings all yield to a base case plus a one-step bridge.
It is the backbone of olympiad proof-writing and underlies the closed forms students conjecture on the AIME via 'find a pattern' — induction is what turns a verified guess into a theorem.
Pitfall: choose the base case where the statement first becomes true and check the inductive step is valid there. $2^n > n^2$ fails for $n = 2, 3, 4$, so a base case of $n = 1$ would leave a gap the dominoes cannot cross — the step only carries from $n = 5$ onward.

Spot the Signal

Look for problems where the key step is proving infinitely many statements by establishing a base case and a reliable step.
You can describe the hard part as proving infinitely many statements by establishing a base case and a reliable step, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the problem-solving bottleneck that calls for mathematical induction, then rewrite the givens around it.
Name the relation that makes Mathematical Induction legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Mathematical Induction just because the surface looks familiar; verify the required condition first.
Applying Mathematical Induction because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let mathematical induction reveal the strategic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is proving infinitely many statements by establishing a base case and a reliable step.

Back to techniques

Problem-Solving StrategyDifficulty 30-95774 tagged problems

Mathematical Induction

Practice this technique Match my level

The Key Result

$$P(1)\text{ true}\quad\text{and}\quad \big(P(k)\Rightarrow P(k+1)\big)\ \forall k \;\;\Longrightarrow\;\; P(n)\ \text{true } \forall n \ge 1.$$

Prove a statement for the first case, then prove that whenever it holds for one case it holds for the next, and it follows for all cases at once — like toppling an infinite line of dominoes.

Why It Works

1
Base case: verify $P(1)$ directly.
2
Inductive hypothesis: assume $P(k)$ is true for an arbitrary fixed $k \ge 1$.
3
Inductive step: using that assumption, prove $P(k+1)$.
4
Since $P(1)$ holds and each true case forces the next, every $P(n)$ holds: the dominoes fall from $1$ onward without gap.

Worked Examples

Example 1

Prove that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for every positive integer $n$.

1
Base case $n=1$: the left side is $1$ and the right side is $\frac{1\cdot 2}{2} = 1$, so $P(1)$ holds.
2
Assume $P(k)$: $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$.
3
Add $k+1$ to both sides: $1 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$.
4
That is exactly $P(k+1)$, so by induction the formula holds for all $n \ge 1$.

Answer:

$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \ge 1$.

Contest level

Prove that $n^3 - n$ is divisible by $6$ for every positive integer $n$.

1
Base case $n = 1$: $1^3 - 1 = 0$, and $6 \mid 0$, so $P(1)$ holds.
2
Assume $P(k)$: $6 \mid k^3 - k$.
3
Expand the next case: $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1)$.
4
The first term is divisible by $6$ by hypothesis; $k(k+1)$ is a product of two consecutive integers, hence even, so $3k(k+1)$ is divisible by $6$. Their sum is divisible by $6$, giving $P(k+1)$.

Answer:

$6 \mid n^3 - n$ for all $n \ge 1$.

Olympiad / Challenge

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

1
Base case $n = 5$: $2^5 = 32 > 25 = 5^2$, so the claim holds at the starting value. (Note it fails at $n = 4$, where $2^4 = 4^2 = 16$, so $n = 5$ is the right base.)
2
Assume $2^k > k^2$ for some $k \ge 5$.
3
Then $2^{k+1} = 2 \cdot 2^k > 2k^2$. It remains to show $2k^2 \ge (k+1)^2$.
4
Since $2k^2 - (k+1)^2 = k^2 - 2k - 1 = (k-1)^2 - 2 \ge (5-1)^2 - 2 = 14 > 0$ for $k \ge 5$, we get $2^{k+1} > 2k^2 \ge (k+1)^2$, which is $P(k+1)$.

Answer:

$2^n > n^2$ for all $n \ge 5$.

Going Deeper

Induction proves far more than summation formulas: divisibility ($6 \mid n^3 - n$), inequalities ($2^n > n^2$), and structural claims about trees, graphs, and tilings all yield to a base case plus a one-step bridge.
It is the backbone of olympiad proof-writing and underlies the closed forms students conjecture on the AIME via 'find a pattern' — induction is what turns a verified guess into a theorem.
Pitfall: choose the base case where the statement first becomes true and check the inductive step is valid there. $2^n > n^2$ fails for $n = 2, 3, 4$, so a base case of $n = 1$ would leave a gap the dominoes cannot cross — the step only carries from $n = 5$ onward.

Spot the Signal

Look for problems where the key step is proving infinitely many statements by establishing a base case and a reliable step.
You can describe the hard part as proving infinitely many statements by establishing a base case and a reliable step, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the problem-solving bottleneck that calls for mathematical induction, then rewrite the givens around it.
Name the relation that makes Mathematical Induction legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Mathematical Induction just because the surface looks familiar; verify the required condition first.
Applying Mathematical Induction because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let mathematical induction reveal the strategic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is proving infinitely many statements by establishing a base case and a reliable step.