IB Math AA: Proof by Induction

Proof by mathematical induction is a powerful technique that allows you to establish the truth of an infinite number of cases with a logical, finite argument. In IB Math Analysis and Approaches HL, this method is not only a frequent exam topic but also a fundamental tool for developing the rigorous reasoning required for advanced mathematics. Mastering induction will enable you to confidently prove statements about summation formulas, divisibility, inequalities, and sequences, forming a cornerstone of your analytical skill set.

The Principle of Mathematical Induction

At its heart, mathematical induction is based on a simple, intuitive idea often compared to knocking over a line of dominoes. If you can knock over the first domino (the base case), and you can prove that whenever one domino falls it will knock over the next one (the inductive step), then all dominoes will fall. Formally, to prove a statement $P(n)$ is true for all natural numbers $n$ (often starting at $n=1$), you must complete two critical steps.

First, you verify the base case. This means proving that the statement $P(n)$ is true for the initial value, typically $n=1$. For example, if you want to prove a formula for the sum of the first $n$ integers, you would check that it holds when $n=1$. This step is often simple but absolutely essential; a failed base case means the entire proof collapses.

Second, you execute the inductive step. Here, you assume that the statement is true for some arbitrary natural number $k$; this assumption is called the inductive hypothesis. Your task is to use this hypothesis to logically demonstrate that the statement must then also be true for $n=k+1$. The structure is: assume $P(k)$ is true, and then prove $P(k+1)$ is true. Successfully linking $P(k)$ to $P(k+1)$ completes the inductive chain, proving $P(n)$ for all $n$. This process cultivates the precise logical reasoning that the IB curriculum emphasizes.

Applying Induction to Summation Formulas

Summation formulas are classic candidates for inductive proofs. Let's prove the well-known result for the sum of the first $n$ positive integers: $1+2+3+...+n=\frac{n(n+1)}{2}$ for all $n\ge 1$.

• Base Case ($n=1$): The left-hand side (LHS) is 1. The right-hand side (RHS) is $\frac{1(1+1)}{2}=\frac{2}{2}=1$. Since LHS = RHS, 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 need 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)& =\left(1+2+...+k\right)+(k+1)\\ & =\frac{k(k+1)}{2}+(k+1)\text{(by the inductive hypothesis)}\\ & =(k+1)\left(\frac{k}{2}+1\right)\\ & =(k+1)\left(\frac{k+2}{2}\right)\\ & =\frac{(k+1)(k+2)}{2}\end{array}$$ This is exactly the result we needed. Therefore, by the principle of mathematical induction, the formula is true for all $n\ge 1$.

This step-by-step manipulation—using the hypothesis to build the case for $k+1$—is the core skill. Exam questions often present similar summation identities, and your solution must mirror this clear, logical structure.

Induction for Divisibility Statements

Induction is equally effective for proving that an expression is divisible by a certain number for all natural numbers $n$. Consider the statement: "$n^3-n$ is divisible by 6 for all $n\ge 1$."

• Base Case ($n=1$): $1^3-1=0$, and 0 is divisible by 6. Base case verified.
• Inductive Hypothesis: Assume the statement is true for $n=k$. That is, assume $k^3-k$ is divisible by 6. This means $k^3-k=6m$ for some integer $m$.
• Inductive Step (Prove for $n=k+1$): Consider $(k+1{)}^3-(k+1)$. We expand and rearrange:

$$\begin{array}{rl}(k+1{)}^3-(k+1)& =(k^3+3k^2+3k+1)-(k+1)\\ & =k^3+3k^2+3k+1-k-1\\ & =k^3+3k^2+2k\\ & =(k^3-k)+(3k^2+3k)\text{(adding and subtracting −k would not help, so we try a different regrouping)}\\ & =(k^3-k)+3k(k+1)\end{array}$$ We know by the hypothesis that $(k^3-k)$ is divisible by 6. Now, notice that $k(k+1)$ is the product of two consecutive integers, which is always even. Therefore, $3k(k+1)$ is divisible by 3 and by 2, making it divisible by 6. The sum of two terms each divisible by 6 is itself divisible by 6. Hence, $(k+1{)}^3-(k+1)$ is divisible by 6.

The key here was to cleverly reorganize the expression for $k+1$ into a part that matches the inductive hypothesis and another part whose divisibility we can argue independently—a common strategy in divisibility proofs.

Tackling Inequalities and Sequence Properties

Inductive proofs extend naturally to inequalities and properties defined by recurrence relations, often requiring more careful algebraic handling. Prove that $2^n>n^2$ for all integers $n\ge 5$.

• Base Case ($n=5$): $2^5=32$ and $5^2=25$. Since $32>25$, the base case holds.
• Inductive Hypothesis: Assume $2^k>k^2$ is true for some $k\ge 5$.
• Inductive Step (Prove for $n=k+1$): We need to show $2^{k+1}>(k+1{)}^2$. Start with the left side:

$$2^{k+1}=2\cdot 2^k$$ By the inductive hypothesis, $2^k>k^2$, so: $$2\cdot 2^k>2\cdot k^2$$ We now need to show that $2k^2\ge (k+1{)}^2$ for $k\ge 5$ to complete the chain. Expand $(k+1{)}^2=k^2+2k+1$. So, we check if $2k^2\ge k^2+2k+1$. This simplifies to $k^2-2k-1\ge 0$. For $k=5$, $25-10-1=14\ge 0$, and since $k^2-2k-1$ is increasing for $k>1$, the inequality holds for all $k\ge 5$. Therefore: $$2^{k+1}>2k^2\ge (k+1{)}^2$$ which proves $2^{k+1}>(k+1{)}^2$.

For sequence properties, such as those defined by $a_{n+1}=2a_n+1$, you would use induction to prove a closed-form formula for $a_n$. The approach is identical: verify the formula for the first term, assume it for $a_k$, and then show it must hold for $a_{k+1}$ using the recurrence relation.

Common Pitfalls

Even with a solid grasp of the steps, several common errors can undermine an inductive proof.

1. Skipping or Incorrectly Verifying the Base Case. It's tempting to jump to the inductive step, but if the statement is false for the starting value, the entire proof is invalid. Correction: Always explicitly state and verify the base case for the smallest $n$ specified in the problem. For statements claiming validity from $n=0$ or $n=5$, your base case must start there.

1. Misapplying the Inductive Hypothesis. The hypothesis is an assumption that $P(k)$ is true to help you prove $P(k+1)$. A frequent mistake is to assume $P(k+1)$ is true from the outset, leading to circular reasoning. Correction: Your proof for $P(k+1)$ must begin with the expression for $k+1$ and then manipulate it until you can cleanly substitute or apply the assumed truth of $P(k)$.

1. Faulty Algebraic or Logical Manipulation. In the inductive step, especially with inequalities or divisibility, a single misstep in algebra or an incorrect inequality sign reversal can break the proof. Correction: Work slowly and justify each manipulation. For inequalities, clearly state when you are using the inductive hypothesis. Test your logic with a concrete numerical example if unsure.

1. Neglecting to State the Conclusion. After completing both steps, you must formally conclude that by the principle of mathematical induction, the statement is true for all $n$. Omitting this conclusion can cost you marks in an exam setting. Correction: Always end your proof with a sentence like: "Therefore, by mathematical induction, $P(n)$ is true for all $n\ge [startingvalue]$."

Summary

• Mathematical induction consists of two mandatory steps: verifying the base case and performing the inductive step (assuming $P(k)$ to prove $P(k+1)$).
• It is a versatile tool for rigorously proving statements about summation formulas, divisibility, inequalities, and sequence properties for all natural numbers.
• The inductive hypothesis is a tool to be used, not a fact to be proven; your task is to show how $P(k)$ logically necessitates $P(k+1)$.
• In exams, present your proof clearly in three distinct parts: Base Case, Inductive Hypothesis, and Inductive Step, followed by a concluding statement.
• Avoid common traps by carefully checking your base case, never assuming what you need to prove, and ensuring flawless algebra in the inductive step.
• Mastering this technique builds the logical foundation essential for higher mathematics, directly assessing the IB's focus on analytical reasoning and proof.