Hey everyone! Ever seen one of those massive, intricate domino setups? You tap the first one, and it sets off a chain reaction, guaranteeing that every single domino will eventually fall. What if I told you there’s a way to do that in mathematics—to prove a statement is true for an infinite number of cases, just by showing the first one works and that each case triggers the next? That’s the magic of mathematical induction. Today, we’re going to unravel this powerful proof technique, which is a must-know for any serious IB Math student. Forget boring definitions; we’re going to see how a simple idea about a viral social media post can help us prove something for all positive integers. Let’s get started!
Table of Contents
What is Mathematical Induction?
Before we dive into solving problems, let’s get the main idea down. At its heart, mathematical induction is a structured way to prove that a statement, which we often call $P(n)$, is true for all natural numbers (or any infinite set of integers starting from a specific point). It’s not a formula, but a logical argument—a beautiful piece of mathematical reasoning.
Definition: Mathematical Induction
Mathematical Induction is a proof technique used to establish that a given statement, $P(n)$, holds for all natural numbers $n$ (or for all integers $n \geq n_0$, where $n_0$ is some starting integer). The proof consists of two main parts: proving a Base Case and proving the Inductive Step.
Think back to our domino analogy. To know for sure that all dominoes will fall, you only need to confirm two things:
- The first domino will fall. (You have to push it!)
- If any given domino falls, it will definitely knock over the next one. (They are spaced correctly.)
If both of these conditions are met, you can walk away confident that the entire infinite line of dominoes will topple. That’s precisely what we do in an induction proof.
The Four-Step Process
Every solid proof by induction follows a clear, four-step structure. If you memorize this structure, you’ll always have a roadmap to follow.
Step 1: The Base Case
This is where you knock over the first domino. You need to show that your statement $P(n)$ is true for the very first value of $n$ specified in the problem (usually $n=1$). You do this by substituting $n=1$ into both sides of your equation (LHS and RHS) and showing they are equal. It’s often the easiest step, but it’s absolutely essential!
Step 2: The Inductive Hypothesis
Here, we make a powerful assumption. We assume that our statement $P(n)$ is true for some arbitrary integer, let’s call it $k$, where $k \geq 1$. You’re not proving anything here; you are simply stating your assumption clearly. You’ll write something like: “Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$. That is, assume [your statement with ‘k’ instead of ‘n’].”
Step 3: The Inductive Step
This is the heart of the proof and where most of the algebra happens. Your goal is to show that if your assumption (the Inductive Hypothesis, $P(k)$) is true, then the statement must also be true for the next integer, $k+1$. Symbolically, you’re proving that $P(k) \implies P(k+1)$. You will start with one side of the $P(k+1)$ statement (usually the more complex side) and use algebraic manipulation—and your Inductive Hypothesis—to show that it equals the other side.
Step 4: The Conclusion
The final flourish. After successfully completing the first three steps, you write a concluding statement that ties everything together. It usually sounds something like this: “Since the base case is true, and it has been shown that $P(k) \implies P(k+1)$, by the Principle of Mathematical Induction, the statement $P(n)$ is true for all positive integers $n$.”
A Viral Challenge: Worked Example
Let’s put this process into action with a fresh problem. No pyramid schemes here—let’s talk about something a bit more modern: a viral social media challenge.
Example: The Viral Post Challenge
Problem: A new viral post starts. In the first hour, the original creator shares it with 4 friends. In the second hour, each of those 4 friends shares it with 4 new people. This pattern continues, with everyone who received the post in the previous hour sharing it with 4 new people. We want to find a formula for the total number of new people who receive the post after $n$ hours. Formulate a hypothesis and prove it is true for all positive integers $n$ using mathematical induction.
Part 1: Formulating the Hypothesis
Let’s look at the pattern of *new* shares each hour:
- Hour 1: $4$ new people ($=4^1$)
- Hour 2: $4 \times 4 = 16$ new people ($=4^2$)
- Hour 3: $16 \times 4 = 64$ new people ($=4^3$)
The total number of new people reached after $n$ hours, $S_n$, is the sum: $S_n = 4^1 + 4^2 + 4^3 + \dots + 4^n$.
This is a geometric series with first term $a=4$ and common ratio $r=4$. Using the sum formula $S_n = \frac{a(r^n – 1)}{r-1}$:
$S_n = \frac{4(4^n – 1)}{4-1} = \frac{4}{3}(4^n – 1)$
Our Hypothesis, $P(n)$, is: $\sum\limits\limits_{i=1}^n 4^i = \frac{4}{3}(4^n – 1)$
Part 2: Proof by Mathematical Induction
Step 1: Base Case (n=1)
We need to check if $P(1)$ is true.
LHS: $\sum\limits_{i=1}^1 4^i = 4^1 = 4$
RHS: $\frac{4}{3}(4^1 – 1) = \frac{4}{3}(3) = 4$
Since LHS = RHS, $P(1)$ is true. The first domino has fallen!
Step 2: Inductive Hypothesis
Assume $P(k)$ is true for some positive integer $k$.
That is, we assume: $\sum\limits_{i=1}^k 4^i = \frac{4}{3}(4^k – 1)$
Step 3: Inductive Step
We need to prove that $P(k) \implies P(k+1)$. Our goal is to show that $\sum\limits_{i=1}^{k+1} 4^i = \frac{4}{3}(4^{k+1} – 1)$.
Let’s start with the LHS of $P(k+1)$:
LHS $= \sum\limits_{i=1}^{k+1} 4^i$
Let’s split the sum to isolate the part from our hypothesis:
$= (\sum\limits_{i=1}^k 4^i) + 4^{k+1}$
Now, substitute using our Inductive Hypothesis:
$= [\frac{4}{3}(4^k – 1)] + 4^{k+1}$
Time for some algebra. Let’s expand and find a common denominator:
$= \frac{4}{3} \cdot 4^k – \frac{4}{3} + 4^{k+1}$
$= \frac{1}{3} \cdot 4 \cdot 4^k – \frac{4}{3} + 4^{k+1}$
$= \frac{1}{3} \cdot 4^{k+1} – \frac{4}{3} + 4^{k+1}$
Group the terms with $4^{k+1}$:
$= (\frac{1}{3} + 1) \cdot 4^{k+1} – \frac{4}{3}$
$= \frac{4}{3} \cdot 4^{k+1} – \frac{4}{3}$
Factor out the common $\frac{4}{3}$:
$= \frac{4}{3}(4^{k+1} – 1)$
This is exactly the RHS of $P(k+1)$! We’ve successfully shown that if $P(k)$ is true, then $P(k+1)$ must also be true.
Step 4: Conclusion
Since $P(1)$ is true, and we have shown that $P(k) \implies P(k+1)$, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.
Therefore, the total number of new people reached by the viral post after $n$ hours is given by the formula $\frac{4}{3}(4^n – 1)$.
IB Tips & Common Mistakes
Mastering induction for the IB exam involves knowing the process and avoiding common pitfalls. Here are a few tips from my experience.
Tip: This Isn’t in the Formula Booklet!
A crucial reminder: Mathematical Induction is a method of proof, not a formula. You will not find the steps listed in your IB Math Formula Booklet. You must understand and memorize the logical structure of the four steps. Practice is the only way to make it second nature.
Hint: Perfect for Your Math IA
If you’re exploring patterns for your Internal Assessment (IA), induction can be a fantastic way to add rigor and mathematical sophistication. For example, if you find a pattern while exploring fractals or sequences and formulate a conjecture (a hypothesis), you can use induction to formally prove it. This demonstrates a high level of mathematical understanding. Just be sure every single algebraic step in your inductive step is crystal clear and well-explained!
Wrapping Up
Mathematical induction can seem intimidating at first, but it’s really just a formal way of capturing that ‘chain reaction’ logic. By mastering the four-step process—Base Case, Inductive Hypothesis, Inductive Step, and Conclusion—you unlock a tool that can prove an infinite number of cases with a finite amount of work. It’s elegant, powerful, and a huge asset in your IB Math toolkit.
Have questions or want to discuss a problem? Share your thoughts in the comments below! Engaging with the material and your peers is a fantastic way to deepen your understanding and analytical skills in mathematics.
Additional Practice
Question 1: Prove that for all positive integers $n$, the sum of the first $n$ even numbers is given by the formula $\sum\limits\limits_{i = 1}^n 2i = n(n+1)$.
Show Answer
Solution:
Base Case (n=1): LHS = $\sum\limits_{i=1}^1 2i = 2$. RHS = $1(1+1) = 2$. $P(1)$ is true.
Inductive Hypothesis: Assume $\sum\limits_{i=1}^k 2i = k(k+1)$ for some $k \in \mathbb{Z}^+$.
Inductive Step: We want to prove $\sum\limits_{i=1}^{k+1} 2i = (k+1)(k+2)$.
LHS = $(\sum\limits_{i=1}^k 2i) + 2(k+1) = k(k+1) + 2(k+1) = (k+1)(k+2)$ = RHS.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{Z}^+$.
Question 2: Prove by induction that $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \geq 1$.
Show Answer
Solution:
Base Case (n=1): LHS = $1^2 = 1$. RHS = $\frac{1(2)(3)}{6} = 1$. $P(1)$ is true.
Inductive Hypothesis: Assume $\sum\limits_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$ for some $k \in \mathbb{Z}^+$.
Inductive Step: We want to prove $\sum\limits_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$.
LHS = $(\sum\limits_{i=1}^k i^2) + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$
$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1)+6(k+1)]}{6}$
$= \frac{(k+1)[2k^2+k+6k+6]}{6} = \frac{(k+1)(2k^2+7k+6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$ = RHS.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \geq 1$.
Question 3: Prove that $7^n – 1$ is divisible by 6 for all positive integers $n$.
Show Answer
Solution:
Base Case (n=1): $7^1 – 1 = 6$. 6 is divisible by 6. $P(1)$ is true.
Inductive Hypothesis: Assume $7^k – 1$ is divisible by 6 for some $k \in \mathbb{Z}^+$. This means $7^k – 1 = 6m$ for some integer $m$, so $7^k = 6m+1$.
Inductive Step: We want to prove $7^{k+1} – 1$ is divisible by 6.
$7^{k+1} – 1 = 7 \cdot 7^k – 1$. Substitute $7^k$ from the hypothesis:
$= 7(6m+1) – 1 = 42m + 7 – 1 = 42m + 6 = 6(7m+1)$.
Since $7m+1$ is an integer, $6(7m+1)$ is divisible by 6.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{Z}^+$.
Question 4: Prove that for all $n \geq 1$, $1 + 4 + 7 + \dots + (3n-2) = \frac{n(3n-1)}{2}$.
Show Answer
Solution:
Base Case (n=1): LHS = $3(1)-2=1$. RHS = $\frac{1(3(1)-1)}{2} = \frac{2}{2} = 1$. $P(1)$ is true.
Inductive Hypothesis: Assume $\sum\limits_{i=1}^k (3i-2) = \frac{k(3k-1)}{2}$ for some $k \in \mathbb{Z}^+$.
Inductive Step: We want to prove $\sum\limits_{i=1}^{k+1} (3i-2) = \frac{(k+1)(3(k+1)-1)}{2} = \frac{(k+1)(3k+2)}{2}$.
LHS = $(\sum\limits_{i=1}^k (3i-2)) + (3(k+1)-2) = \frac{k(3k-1)}{2} + (3k+1)$
$= \frac{3k^2-k+2(3k+1)}{2} = \frac{3k^2-k+6k+2}{2} = \frac{3k^2+5k+2}{2} = \frac{(k+1)(3k+2)}{2}$ = RHS.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \geq 1$.
Question 5: Prove that $n^3 + 2n$ is divisible by 3 for all $n \in \mathbb{Z}^+$.
Show Answer
Solution:
Base Case (n=1): $1^3 + 2(1) = 3$. 3 is divisible by 3. $P(1)$ is true.
Inductive Hypothesis: Assume $k^3 + 2k$ is divisible by 3 for some $k \in \mathbb{Z}^+$. So, $k^3+2k = 3m$ for some integer $m$.
Inductive Step: We want to prove $(k+1)^3 + 2(k+1)$ is divisible by 3.
$(k+1)^3 + 2(k+1) = (k^3+3k^2+3k+1) + (2k+2)$
$= (k^3+2k) + 3k^2 + 3k + 3 = (k^3+2k) + 3(k^2+k+1)$.
From the hypothesis, $k^3+2k$ is divisible by 3. And $3(k^2+k+1)$ is clearly divisible by 3. The sum of two numbers divisible by 3 is also divisible by 3.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{Z}^+$.
Question 6: Prove by induction that $2^n > n$ for all positive integers $n$.
Show Answer
Solution:
Base Case (n=1): $2^1 > 1$, which is $2 > 1$. True. $P(1)$ is true.
Inductive Hypothesis: Assume $2^k > k$ for some $k \in \mathbb{Z}^+$.
Inductive Step: We want to prove $2^{k+1} > k+1$.
LHS = $2^{k+1} = 2 \cdot 2^k$. From the hypothesis, $2^k > k$, so $2 \cdot 2^k > 2k$.
So, we have $2^{k+1} > 2k$. Now we need to show that $2k \geq k+1$.
$2k – k \geq 1 \implies k \geq 1$. Since our domain is for all positive integers, this is true.
Therefore, $2^{k+1} > 2k \geq k+1$, which implies $2^{k+1} > k+1$.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{Z}^+$.
Question 7: Prove that for any integer $n \geq 1$, the number of diagonals in a convex polygon with $n+2$ sides is $\frac{(n+2)(n-1)}{2}$. (Hint: Use $n$ for induction, corresponding to a polygon with $n+2$ sides).
Show Answer
Solution:
Let $P(n)$ be the statement for a polygon with $n+2$ sides. The base case for a polygon is a triangle ($n=1$, 3 sides).
Base Case (n=1, a triangle): Sides = $1+2=3$. Number of diagonals is 0. Formula gives $\frac{(1+2)(1-1)}{2} = 0$. $P(1)$ is true.
Inductive Hypothesis: Assume for a polygon with $k+2$ sides, the number of diagonals is $\frac{(k+2)(k-1)}{2}$.
Inductive Step: Consider a polygon with $(k+1)+2 = k+3$ sides. We can form this by taking a polygon with $k+2$ sides and adding a vertex. When we add a vertex, we replace one side with two new sides, and we can draw new diagonals from this new vertex to all other vertices except its two adjacent ones. This adds $(k+3)-3 = k$ new diagonals. Plus, the side that was replaced becomes a new diagonal. Total added diagonals = $k+1$.
Total diagonals = (diagonals in $(k+2)$-gon) + $(k+1) = \frac{(k+2)(k-1)}{2} + (k+1)$
$= \frac{k^2+k-2+2k+2}{2} = \frac{k^2+3k}{2} = \frac{k(k+3)}{2}$.
The formula for $n=k+1$ gives $\frac{((k+1)+2)((k+1)-1)}{2} = \frac{(k+3)k}{2}$. They match.
Conclusion: By the Principle of Mathematical Induction, the formula is true for all $n \geq 1$.
Question 8: Prove that $4^n + 15n – 1$ is divisible by 9 for all positive integers $n$.
Show Answer
Solution:
Base Case (n=1): $4^1 + 15(1) – 1 = 4+15-1=18$. 18 is divisible by 9. $P(1)$ is true.
Inductive Hypothesis: Assume $4^k + 15k – 1 = 9m$ for some integer $m$. So, $4^k = 9m – 15k + 1$.
Inductive Step: We want to prove $4^{k+1} + 15(k+1) – 1$ is divisible by 9.
$4^{k+1} + 15k + 15 – 1 = 4 \cdot 4^k + 15k + 14$. Substitute $4^k$:
$= 4(9m – 15k + 1) + 15k + 14 = 36m – 60k + 4 + 15k + 14$
$= 36m – 45k + 18 = 9(4m – 5k + 2)$. This is divisible by 9.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{Z}^+$.
Question 9: Prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}$ for all $n \geq 1$.
Show Answer
Solution:
Base Case (n=1): LHS = $\frac{1}{1 \cdot 2} = \frac{1}{2}$. RHS = $\frac{1}{1+1} = \frac{1}{2}$. $P(1)$ is true.
Inductive Hypothesis: Assume $\sum\limits_{i=1}^k \frac{1}{i(i+1)} = \frac{k}{k+1}$.
Inductive Step: We want to prove $\sum\limits_{i=1}^{k+1} \frac{1}{i(i+1)} = \frac{k+1}{k+2}$.
LHS = $(\sum\limits_{i=1}^k \frac{1}{i(i+1)}) + \frac{1}{(k+1)(k+2)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)}$
$= \frac{k(k+2)+1}{(k+1)(k+2)} = \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$ = RHS.
Conclusion: By the Principle of Mathematical Induction, the statement is true for all $n \geq 1$.
IB Exam Style Question
Question 10: Use the principle of mathematical induction to prove that $n^3 – n$ is divisible by 6 for all integers $n \geq 2$.
Show Answer
Solution:
Let $P(n)$ be the statement “$n^3 – n$ is divisible by 6”.
Base Case (n=2): $2^3 – 2 = 8 – 2 = 6$. Since 6 is divisible by 6, $P(2)$ is true.
Inductive Hypothesis: Assume $P(k)$ is true for some integer $k \geq 2$. That is, assume $k^3 – k$ is divisible by 6. This implies $k^3 – k = 6m$ for some integer $m$.
Inductive Step: We want to show that $P(k+1)$ is true, i.e., that $(k+1)^3 – (k+1)$ is divisible by 6.
Consider the expression for $P(k+1)$:
$(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$
Now, let’s rearrange the terms to use our inductive hypothesis ($k^3 – k$):
$= (k^3 – k) + 3k^2 + 3k$
From our hypothesis, we know that $(k^3 – k)$ is divisible by 6.
Now we need to analyze the remaining part: $3k^2 + 3k = 3k(k+1)$.
The term $k(k+1)$ represents the product of two consecutive integers. One of these integers must be even. Therefore, $k(k+1)$ is always divisible by 2. Let $k(k+1) = 2j$ for some integer $j$.
So, $3k(k+1) = 3(2j) = 6j$. This shows that $3k(k+1)$ is always divisible by 6.
We have shown that $(k+1)^3 – (k+1)$ is the sum of two terms, $(k^3 – k)$ and $3k(k+1)$, both of which are divisible by 6. The sum of two multiples of 6 is also a multiple of 6.
Conclusion: Since $P(2)$ is true, and we have shown that if $P(k)$ is true then $P(k+1)$ is also true, by the Principle of Mathematical Induction, the statement $n^3 – n$ is divisible by 6 for all integers $n \geq 2$.