Pre-Calculus: Introduction to Mathematical Induction

How do you prove a statement is true for every single positive integer, from one to infinity? You cannot possibly check each case individually. Mathematical induction is a powerful proof technique that solves this exact problem, allowing you to establish the truth of an infinite sequence of statements with a finite, logical argument. Mastering induction is not just a pre-calculus milestone; it is foundational for advanced mathematics, computer science, and engineering, where reasoning about discrete, sequential processes is essential.

The Principle of Mathematical Induction

At its heart, mathematical induction is based on a simple, domino-like principle. Imagine you have an infinite line of dominoes. If you can prove that (1) the first domino falls (the base case), and (2) whenever any arbitrary domino falls, it will knock over the next one (the inductive step), then you can conclude that all dominoes will fall.

Formally, to prove a statement $P(n)$ is true for all natural numbers $n$ (typically starting at $n=1$ or $n=0$), you must complete two steps:

1. Base Case: Prove that $P(1)$ (or your starting index) is true. This is the foundation of your proof.
2. Inductive Step: Assume that $P(k)$ is true for some arbitrary integer $k\ge 1$. This assumption is called the inductive hypothesis. Using this hypothesis, you must then prove that $P(k+1)$ is also true.

The logical power comes from the word "arbitrary." You don't assume it for a specific number, but for a general $k$. Proving the step shows that if the statement holds at any given rung of the ladder, it must also hold on the very next rung. Combined with the base case, this creates an unstoppable chain of truth: $P(1)$ is true, so $P(2)$ is true; since $P(2)$ is true, $P(3)$ is true, and so on, ad infinitum.

Proving Summation Formulas

A classic application of induction is verifying formulas for the sums of series. Let's prove that the sum of the first $n$ positive integers is given by the formula $1+2+3+...+n=\frac{n(n+1)}{2}$.

• Statement: Let $P(n)$ be the statement: $1+2+3+...+n=\frac{n(n+1)}{2}$.
• Base Case ($n=1$): Check the left side: $1$. Check the right side: $\frac{1(1+1)}{2}=1$. They are equal, so $P(1)$ is true.
• Inductive Hypothesis: Assume $P(k)$ is true for some arbitrary $k\ge 1$. That is, assume:

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

• Inductive Step (Prove $P(k+1)$): We must prove that $P(k+1)$ is true, which states:

$$1+2+3+...+k+(k+1)=\frac{(k+1)((k+1)+1)}{2}=\frac{(k+1)(k+2)}{2}$$ Start with the left side of $P(k+1)$ and use the inductive hypothesis: $$[1+2+3+...+k]+(k+1)=\frac{k(k+1)}{2}+(k+1)$$ Now, combine the terms into a single fraction: $$=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{k(k+1)+2(k+1)}{2}$$ Factor out $(k+1)$: $$=\frac{(k+1)(k+2)}{2}$$ This is exactly the right side of $P(k+1)$. Therefore, $P(k+1)$ is true if $P(k)$ is true.

Since both the base case and the inductive step have been verified, by the principle of mathematical induction, the formula $1+2+3+...+n=\frac{n(n+1)}{2}$ is true for all positive integers $n$.

Applying Induction to Inequalities

Induction is not limited to equations; it is equally effective for proving inequalities. Let's prove that $2^n>n$ for all integers $n\ge 1$.

• Statement: $P(n):2^n>n$.
• Base Case ($n=1$): $2^1=2>1$. True.
• Inductive Hypothesis: Assume $P(k)$ is true: $2^k>k$.
• Inductive Step (Prove $P(k+1):2^{k+1}>k+1$):

Start with the left side of $P(k+1)$: $$2^{k+1}=2\cdot 2^k$$ Now, apply the inductive hypothesis ($2^k>k$): $$2\cdot 2^k>2\cdot k=2k$$ To finish, we need to show $2k\ge k+1$. This holds for all $k\ge 1$ because $2k=k+k\ge k+1$. Therefore: $$2^{k+1}>2k\ge k+1$$ which implies $2^{k+1}>k+1$. Thus, $P(k+1)$ is true.

By induction, $2^n>n$ for all $n\ge 1$.

Proving Divisibility Statements

Induction provides a structured way to prove that one expression divides another for all natural numbers. Prove that $n^3-n$ is divisible by 3 for all $n\ge 1$.

• Statement: $P(n):3\mid (n^3-n)$ (read as "3 divides $n^3-n$").
• Base Case ($n=1$): $1^3-1=0$, and 3 divides 0. True.
• Inductive Hypothesis: Assume $P(k)$ is true: $3\mid (k^3-k)$. This means $k^3-k=3m$ for some integer $m$.
• Inductive Step (Prove $P(k+1):3\mid ((k+1{)}^3-(k+1)$)):

Consider the expression for $n=k+1$: $$(k+1{)}^3-(k+1)=(k^3+3k^2+3k+1)-k-1=k^3+3k^2+3k-k$$ Simplify and strategically regroup: $$=(k^3-k)+(3k^2+3k)$$ The first term, $(k^3-k)$, is divisible by 3 by the inductive hypothesis. The second term, $3k^2+3k=3(k^2+k)$, is clearly a multiple of 3. The sum of two multiples of 3 is itself a multiple of 3. Therefore, $(k+1{)}^3-(k+1)$ is divisible by 3.

Hence, by induction, $n^3-n$ is divisible by 3 for all positive integers $n$.

Common Pitfalls

1. Skipping or Mishandling the Base Case: The most frequent error is proving the inductive step but using a base case that doesn't actually start the chain reaction. For example, if you are proving a statement for $n\ge 5$, your base case must be $n=5$. The inductive step relies on the base case to anchor the entire argument.
2. Confusing the Inductive Hypothesis with What Needs to Be Proved: In the inductive step, you assume $P(k)$ and must prove $P(k+1)$. A common mistake is to start with $P(k+1)$ and, through a series of steps, derive a true statement, which is a logical fallacy (assuming the conclusion). You must connect $P(k+1)$ back to the assumed truth of $P(k)$.
3. Insufficient Algebraic Manipulation: In proofs for summations or divisibility, students often write the expression for $P(k+1)$ but fail to algebraically manipulate it so that the inductive hypothesis $P(k)$ can be directly substituted. The key is to explicitly extract the form of $P(k)$ from within $P(k+1)$.
4. Assuming the Statement is True for All $n$ in the Hypothesis: The inductive hypothesis is "Assume $P(k)$ is true for some arbitrary $k$." It is not "Assume $P(n)$ is true for all $n$." The latter is what you are trying to prove, so assuming it would be circular reasoning.

Summary

• Mathematical induction is a two-step proof technique used to establish that a statement $P(n)$ is true for all natural numbers $n$.
• The base case verifies the statement for the initial number (e.g., $n=1$), providing the foundation for the proof.
• The inductive step involves assuming the statement is true for an arbitrary integer $k$ (the inductive hypothesis) and then proving this assumption forces the statement to also be true for $k+1$.
• Induction is versatile, applicable for proving summation formulas, inequalities, and divisibility statements, among other properties of integers.
• Success depends on careful attention to both steps, clear algebraic manipulation to link $P(k+1)$ to $P(k)$, and avoiding common logical fallacies like assuming the conclusion.