Mathematical Induction

Welcome to Mathematical Induction!

Hello there! Ever wondered how we can prove a mathematical statement is true for every single positive whole number (like 1, 2, 3, and onwards to infinity) without actually testing them all? It seems impossible, right? Well, that's where Mathematical Induction comes in. It's a powerful and elegant proof technique that's a bit like a logical chain reaction.

Don't worry if the name sounds intimidating. Think of it as a recipe. If you follow the steps correctly, you'll get the right result every time. In this chapter, we'll learn this "recipe" to prove statements, especially those involving the sum of sequences.

What is Mathematical Induction? The Domino Effect Analogy

Imagine you have an infinite line of dominoes, one for each positive number (1, 2, 3, ...).

How can you be sure you can knock them ALL down?

You only need to do two things:

  1. Push the first domino over. (This is the starting point).
  2. Make sure that if any domino falls, it will definitely knock over the next one. (This ensures the chain reaction continues forever).

If you can guarantee these two things, you know for certain that all the dominoes will fall. Mathematical Induction works in exactly the same way!

  • The "first domino" is called the Base Case.
  • The "chain reaction" part is called the Inductive Step.

The Three Steps of Mathematical Induction (The "Recipe")

Every proof by Mathematical Induction follows the same logical structure. Let's call the statement we want to prove "P(n)". For example, P(n) could be the statement "$$1+2+...+n = \frac{n(n+1)}{2}$$".

Here are the essential steps. Memorise them!

Step 1: The Base Case (Pushing the first domino)

Your goal here is to prove that the statement P(n) is true for the very first possible value, which is usually n = 1.

  • Substitute n=1 into the left-hand side (LHS) of the equation.
  • Substitute n=1 into the right-hand side (RHS) of the equation.
  • Show that the LHS equals the RHS.

Once you've shown this, you've proven P(1) is true. The first domino has fallen!

Step 2: The Inductive Hypothesis (The Assumption)

This is the "chain reaction" part. We start by making an assumption.

We assume that P(n) is true for some arbitrary positive integer, n = k. This is like assuming some random domino 'k' has fallen over.

All you do in this step is rewrite the original statement P(n) with 'k' instead of 'n'. For example:

"Assume P(k) is true for some positive integer k, so $$1+2+...+k = \frac{k(k+1)}{2}$$"

Important: This is an assumption that you will use in the next step. It's your most important tool!

Step 3: The Inductive Step (Proving the chain reaction)

This is the main part of the proof. Your goal is to show that if P(k) is true (if domino k falls), then P(k+1) must also be true (it knocks over domino k+1).

  1. State your goal: Write down what you need to prove. You want to prove P(k+1) is true. To do this, replace 'n' with 'k+1' in the original statement. This is your "target".
    e.g. We want to prove $$1+2+...+k+(k+1) = \frac{(k+1)((k+1)+1)}{2}$$

  2. Start with the LHS of P(k+1): Write down the Left-Hand Side of your target equation.

  3. Use your assumption from Step 2: This is the key moment! The LHS of P(k+1) will always contain the LHS of P(k). Replace that part with the RHS of your P(k) assumption.

  4. Use algebra: Simplify the expression until it perfectly matches the RHS of your P(k+1) target.
The Conclusion

Once you've completed the three steps, you must write a concluding statement. This is worth marks in an exam!

"By the Principle of Mathematical Induction, P(n) is true for all positive integers n."

Quick Review: Memory Aid "B.A.P.C."
  • B - Base Case: Prove true for n=1.
  • A - Assumption: Assume true for n=k.
  • P - Proof: Prove that if it's true for k, it must be true for k+1.
  • C - Conclusion: Write the final statement.

Let's Walk Through an Example (Summation)

This is the most common type of question you'll see in the HKDSE exam. Let's do one together.

Question: Prove that for all positive integers n, $$1 \times 2 + 2 \times 3 + 3 \times 4 + ... + n(n+1) = \frac{n(n+1)(n+2)}{3}$$

Solution:

Let P(n) be the proposition $$1 \times 2 + 2 \times 3 + ... + n(n+1) = \frac{n(n+1)(n+2)}{3}$$

(B) Base Case: When n = 1,

LHS = $$1(1+1) = 2$$

RHS = $$\frac{1(1+1)(1+2)}{3} = \frac{1 \times 2 \times 3}{3} = 2$$

Since LHS = RHS, P(1) is true.

(A) Assumption:

Assume P(k) is true for some positive integer k.

That is, we assume $$1 \times 2 + 2 \times 3 + ... + k(k+1) = \frac{k(k+1)(k+2)}{3}$$

(P) Proof (Inductive Step):

We want to prove that P(k+1) is true. Our target is to show:

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

Which simplifies to:

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

Now, let's start with the LHS of P(k+1):

LHS = $$[1 \times 2 + 2 \times 3 + ... + k(k+1)] + (k+1)(k+2)$$

(Notice the part in the square brackets is the LHS of our assumption!)

Using the assumption from Step 2, we substitute:

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

Now we use algebra to simplify. Let's find a common denominator:

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

Take out the common factors, which are (k+1) and (k+2):

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

This is exactly the RHS of our P(k+1) target! So we have shown that if P(k) is true, then P(k+1) is also true.

(C) Conclusion:

By the Principle of Mathematical Induction, P(n) is true for all positive integers n.

Common Mistakes to Avoid!

  • Not using the assumption: The biggest mistake! If you don't use your P(k) assumption in the Inductive Step, your proof is incorrect. You haven't linked the dominoes together.
  • Algebra errors: Be very careful when simplifying the expression in the Inductive Step. Take out common factors instead of expanding everything out, as it's usually much easier.
  • Working backwards: Do not start with the P(k+1) equation and work backwards. You must start with the LHS of P(k+1) and, through logical steps, show that it equals the RHS.
  • Forgetting the conclusion: Always write the final concluding sentence. It's an easy mark to get!

Chapter Summary: Key Takeaways

Mathematical Induction is a formal method for proving a statement is true for all positive integers.

The Core Idea: It's like a chain of dominoes. You prove the first one falls (Base Case) and then you prove that any falling domino will always knock over the next one (Inductive Step).

The "B.A.P.C." Method:

  1. Base Case: Show P(1) is true.
  2. Assumption: Assume P(k) is true.
  3. Proof: Use the assumption for P(k) to prove that P(k+1) is true.
  4. Conclusion: Write the final statement.

Practice is the absolute key to mastering this topic. The steps are always the same, but the algebra changes. The more you practice, the more confident you will become. You can do this!