Math AA HL: Proof by Mathematical Induction

Proof by mathematical induction is one of the most powerful and elegant tools in your advanced mathematics toolkit. It allows you to prove that a statement is true for every natural number by connecting an infinite chain of logical implications, much like dominoes falling in sequence. Mastering this technique is non-negotiable for IB Math AA HL, as it develops the rigorous logical reasoning and clear mathematical communication essential for higher-level study.

Understanding the Structure of Inductive Proof

A proof by mathematical induction follows a precise, three-step structure. Think of it as verifying a pattern holds forever. First, you check the first domino can fall. Then, you assume one domino falls, and use that to prove the next one must also fall. If both checks pass, the entire infinite sequence is guaranteed.

The base case is your starting point. You verify that the statement $P(n)$ you want to prove is true for the initial value, typically $n=1$ or sometimes $n=0$. This step is often simple but must be shown explicitly; skipping it is like having no first domino to push.

Next, you state the inductive hypothesis. You assume that the statement $P(k)$ is true for some arbitrary natural number $k$. This is not what you are trying to prove; it is a strategic assumption you are allowed to make. You are saying, "Let's assume, for the sake of argument, that the pattern holds for this one particular step $k$."

The final and most substantive step is the inductive step. Here, you must use the assumption that $P(k)$ is true to deduce that $P(k+1)$ is also true. This is the logical engine of the proof, where you perform algebraic manipulation, apply the hypothesis, and arrive at the statement for $k+1$. Successfully completing this step creates the domino effect: if true for 1, then true for 2; if true for 2, then true for 3, and so on ad infinitum.

Applying Induction to Summation Formulas

Proving formulas for series is the most classic application of induction. It provides a clear, mechanical way to verify closed-form expressions for sums.

Example: Prove that ${\sum }_{r=1}^n{r}^2=\frac{n(n+1)(2n+1)}{6}$ for all $n\in \mathbb{N}$.

• Base Case ($n=1$): LHS = $1^2=1$. RHS = $\frac{1\cdot 2\cdot 3}{6}=1$. True.
• Inductive Hypothesis: Assume the formula holds for $n=k$: ${\sum }_{r=1}^k{r}^2=\frac{k(k+1)(2k+1)}{6}$.
• Inductive Step: Consider the sum for $n=k+1$.

$$\sum _{r=1}^{k+1}{r}^2=\underset{\text{Use hypothesis}}{\underbrace{\sum _{r=1}^k{r}^2}}+(k+1{)}^2$$ Substitute the hypothesis: $$=\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2$$ The goal is to manipulate this expression to match the original formula with $n=k+1$, which would be $\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$. Factor out $\frac{(k+1)}{6}$: $$=\frac{(k+1)}{6}\left[k(2k+1)+6(k+1)\right]=\frac{(k+1)}{6}\left[2k^2+k+6k+6\right]=\frac{(k+1)}{6}\left[2k^2+7k+6\right]$$ Factor the quadratic: $2k^2+7k+6=(k+2)(2k+3)$. Therefore, $$\sum _{r=1}^{k+1}{r}^2=\frac{(k+1)(k+2)(2k+3)}{6}$$ This is precisely $P(k+1)$. The inductive step is complete.

By the principle of mathematical induction, the formula is true for all $n\in \mathbb{N}$. Notice how the hypothesis was used as a direct substitution, transforming the problem into pure algebra.

Proving Divisibility Results

Induction is excellent for proving statements of the form "$f(n)$ is divisible by $d$ for all natural numbers $n$," where $f(n)$ is an expression involving $n$. The strategy in the inductive step is to express $f(k+1)$ in terms of $f(k)$ plus a term that is clearly also divisible by $d$.

Example: Prove that $9^n-1$ is divisible by 8 for all $n\in \mathbb{N}$.

• Base Case ($n=1$): $9^1-1=8$, which is divisible by 8. True.
• Inductive Hypothesis: Assume $9^k-1$ is divisible by 8. This means $9^k-1=8A$ for some integer $A$, or equivalently, $9^k=8A+1$.
• Inductive Step: Consider $9^{k+1}-1$.

$$9^{k+1}-1=9\cdot 9^k-1$$ Substitute the hypothesis ($9^k=8A+1$): $$=9(8A+1)-1=72A+9-1=72A+8=8(9A+1)$$ Since $9A+1$ is an integer, $9^{k+1}-1$ is a multiple of 8. Therefore, if the statement is true for $n=k$, it is true for $n=k+1$.

By induction, $9^n-1$ is divisible by 8 for all $n\in \mathbb{N}$. The key was to cleverly rewrite the expression to make the hypothesis applicable.

Establishing Inequality Statements

Proving inequalities often requires careful manipulation in the inductive step. You start with the assumed inequality $P(k)$ and manipulate it towards the desired inequality $P(k+1)$. Sometimes you need to add or multiply both sides by positive quantities to bridge the gap.

Example: Prove that $2^n>n^2$ for all integers $n\ge 5$.

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

Start with the hypothesis: $2^k>k^2$. Multiply both sides by 2 (a positive number, so inequality direction is preserved): $$2^{k+1}>2k^2$$ Our goal is $(k+1{)}^2=k^2+2k+1$. If we can show $2k^2\ge k^2+2k+1$ for $k\ge 5$, then we are done, because $2^{k+1}>2k^2\ge (k+1{)}^2$ implies $2^{k+1}>(k+1{)}^2$. Check $2k^2\ge k^2+2k+1$: $$2k^2-k^2-2k-1\ge 0⟹k^2-2k-1\ge 0$$ This quadratic holds for $k\ge 1+\sqrt{2}\approx 2.41$. It certainly holds for our case $k\ge 5$. Therefore, $2^{k+1}>2k^2\ge (k+1{)}^2$, so $2^{k+1}>(k+1{)}^2$.

By induction, $2^n>n^2$ for all integers $n\ge 5$. The proof required the extra step of showing an intermediate inequality ($2k^2\ge (k+1{)}^2$) was true under the given conditions.

Common Pitfalls

1. Skipping or Mishandling the Base Case: Never assume the base case is "obvious." You must show the arithmetic. Furthermore, ensure your base case matches the domain. If proving a statement for $n\ge 5$, your base case is $n=5$, not $n=1$.

1. Circular Reasoning in the Inductive Step: A major error is to start the inductive step by assuming $P(k+1)$ is true, then manipulating it to reach a known truth. This is logically backwards. You must begin with $P(k)$ (your hypothesis) and use it to derive $P(k+1)$.

1. Poor Algebraic Manipulation with Inequalities: When proving inequalities, you cannot simply add or multiply inequalities unless you know the terms are positive. For example, from $a>b$, you can deduce $a+c>b+c$ for any real $c$, but you can only deduce $ac>bc$ if $c>0$. If $c$ is negative, the inequality sign flips.

1. Unclear Presentation and Lack of "Scaffolding": A proof is a communicative act. Clearly label your Base Case, Inductive Hypothesis, and Inductive Step. Explain key algebraic manipulations. A string of unexplained equations is difficult to follow and risks losing logical coherence.

Summary

• Mathematical induction is a fundamental proof technique that establishes the truth of a statement $P(n)$ for all natural numbers $n$ by verifying a base case and proving that $P(k)$ implies $P(k+1)$.
• The three-step structure is rigorous: 1) Prove the Base Case, 2) State the Inductive Hypothesis ($P(k)$ is true), 3) Execute the Inductive Step (use the hypothesis to prove $P(k+1)$).
• It is powerfully applied to summation formulas, where the hypothesis is substituted directly into the sum for $k+1$.
• For divisibility results, the goal is to algebraically rearrange $f(k+1)$ to show it consists of $f(k)$ (divisible by the number) plus another term that is also divisible.
• Proving inequalities often requires starting from $P(k)$ and manipulating it towards $P(k+1)$, sometimes needing to prove an auxiliary inequality to complete the logical chain.
• Success hinges on clear logical reasoning, meticulous algebra, and avoiding common traps like circular logic or an incorrect base case.