Pre-Calculus: Mathematical Induction

Mathematical induction is a powerful proof technique that allows you to establish the truth of an infinite number of statements with a finite, logical argument. It’s the go-to method for proving propositions about patterns that hold for all natural numbers, such as formulas for sums, divisibility rules, or inequalities. Mastering induction strengthens your logical reasoning and provides a foundational tool for higher mathematics and computer science.

The Principle and Process of Induction

Think of mathematical induction like an infinite line of dominoes. To be sure every domino will fall, you need to verify two things: first, that you can knock over the initial domino (the base case), and second, that whenever any arbitrary domino falls, it will knock over the next one (the inductive step). This principle forms the backbone of every induction proof.

A proof by mathematical induction follows a strict two-step structure to prove a statement $P(n)$ for all natural numbers $n$, typically starting at $n=1$ or $n=0$.

1. Base Case: Prove that $P(1)$ (or the starting number) is true. This anchors the entire argument.
2. Inductive Step: Assume that $P(k)$ is true for some arbitrary natural number $k$. This assumption is called the inductive hypothesis. Then, using this hypothesis, prove that $P(k+1)$ must also be true.

If both steps are successfully completed, you can conclude that $P(n)$ is true for all natural numbers $n\ge$ your starting number. The power lies in the inductive step: it creates a chain reaction. Since $P(1)$ is true, the inductive step proves $P(2)$ is true. Since $P(2)$ is true, the step proves $P(3)$ is true, and so on, indefinitely.

Proving Summation Formulas

Induction is perfectly suited for proving closed-form formulas for series. Consider the statement: For all natural numbers $n$, $1+2+3+...+n=\frac{n(n+1)}{2}$.

• Base Case ($n=1$): The left side is $1$. The right side is $\frac{1(1+1)}{2}=1$. They are equal, so the base case holds.
• Inductive Hypothesis: Assume the formula is true for $n=k$. That is, assume:

$$1+2+...+k=\frac{k(k+1)}{2}$$

• Inductive Step (Prove for $n=k+1$): We want to show that $1+2+...+k+(k+1)=\frac{(k+1)((k+1)+1)}{2}=\frac{(k+1)(k+2)}{2}$.

Start with the sum for $k+1$ terms and apply the inductive hypothesis: $$\begin{array}{rl}1+2+...+k+(k+1)& =[1+2+...+k]+(k+1)\\ & =\frac{k(k+1)}{2}+(k+1)\text{(by the inductive hypothesis)}\\ & =\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\\ & =\frac{(k+1)(k+2)}{2}\end{array}$$ This is exactly the formula we wanted for $n=k+1$. Therefore, by the principle of mathematical induction, the formula is true for all natural numbers $n$.

Proving Divisibility Properties

Induction can prove that an expression is divisible by a certain integer for all $n$. For example, prove $4$ divides $5^n-1$ for all natural numbers $n$.

• Base Case ($n=1$): $5^1-1=4$, which is divisible by $4$. The base case holds.
• Inductive Hypothesis: Assume $4$ divides $5^k-1$ for some $k\ge 1$. This means $5^k-1=4m$ for some integer $m$, or $5^k=4m+1$.
• Inductive Step (Prove for $n=k+1$): Consider $5^{k+1}-1$.

$$\begin{array}{rl}{5}^{k+1}-1& =5\cdot 5^k-1\\ & =5(4m+1)-1\text{(substituting the inductive hypothesis)}\\ & =20m+5-1\\ & =20m+4\\ & =4(5m+1)\end{array}$$ This is clearly divisible by $4$. Therefore, by induction, $4$ divides $5^n-1$ for all natural numbers $n$.

Proving Inequality Statements

Induction is also effective for proving inequalities. Prove that for all integers $n\ge 5$, $2^n>n^2$.

• Base Case ($n=5$): $2^5=32$ and $5^2=25$. $32>25$, so true.
• Inductive Hypothesis: Assume $2^k>k^2$ for some arbitrary integer $k\ge 5$.
• Inductive Step (Prove for $n=k+1$): We need to show $2^{k+1}>(k+1{)}^2$.

Start with $2^{k+1}=2\cdot 2^k$. Apply the inductive hypothesis: $$2^{k+1}=2\cdot 2^k>2\cdot k^2$$ Now, we need to show that $2k^2\ge (k+1{)}^2$ for $k\ge 5$ to complete the chain. $$2k^2\ge (k+1{)}^2$$ $$2k^2\ge k^2+2k+1$$ $$k^2-2k-1\ge 0$$ The roots of $k^2-2k-1=0$ are $1\pm \sqrt{2}$. For $k\ge 3$, this inequality holds. Since our hypothesis starts at $k\ge 5$, it's valid. Therefore: $$2^{k+1}>2k^2\ge (k+1{)}^2$$ Hence, $2^{k+1}>(k+1{)}^2$, completing the inductive step and the proof.

Common Pitfalls

1. Skipping or Incorrectly Proving the Base Case: The most common error is assuming the base case is trivial or starting with the wrong number. Always prove the base case explicitly. The inductive step shows if one domino falls, the next does; you must prove the first one falls yourself.
2. Misapplying the Inductive Hypothesis: In the inductive step, you must use the assumption that $P(k)$ is true to prove $P(k+1)$. A proof that does not reference the inductive hypothesis is not a valid induction proof. It's just a direct proof for the $k+1$ case.
3. Algebraic or Logical Errors in the Inductive Step: Be meticulous with algebra, especially when proving divisibility or inequalities. A single sign error can break the entire proof. For inequalities, ensure each step preserves the inequality direction.
4. Using $n$ in the Inductive Hypothesis: The hypothesis assumes truth for an arbitrary $k$, not for the specific variable $n$ from the original statement. Writing "Assume $P(n)$ is true" is a major faux pas. Use a different letter ($k$, $m$, $i$) to avoid confusion and highlight the arbitrary nature of the assumption.

Summary

• Mathematical induction is a two-step proof technique used to establish that a statement $P(n)$ is true for all natural numbers $n$ starting from a certain point.
• The base case verifies the initial statement, while the inductive step proves that if the statement holds for an arbitrary case $k$ (the inductive hypothesis), it must also hold for the next case $k+1$.
• Induction is the appropriate and standard technique for proving formulas for sums of series (e.g., $1+2+...+n$), many divisibility properties, and increasing inequalities.
• The core of the inductive step is to connect the expression for $P(k+1)$ back to the assumed truth of $P(k)$, using algebraic manipulation.
• Avoid common errors by carefully proving the base case, explicitly stating and using the inductive hypothesis, and performing flawless algebra in the inductive step.