Yes, I know: you've eagerly started reading this material to know more about induction proofs. And we'll get there! But for the same that reason we cannot (should not) build a house on top of sand, we need to guarantee that your foundation skills are top notch. And which skills are we talking about? Most importantly, factoring polynomials, dealing with rational expressions and exponents. We'll start with factoring.

Factoring

Factoring polynomials

Of all the skills necessary in induction proofs, factoring polynomials is probably the most important one. There are many steps in an induction proof however factoring polynomials is a skill that will show up in the vast majority of them. You should be completely comfortable with all exercises and processes in this lesson.

Greatest common factor

The initial approach to factoring polynomials involves extracting the greatest common factor (GCF). In fact, whenever we attempt to factor any polynomial, this is typically the first step to consider, as it can significantly simplify the expression.

To apply this technique, we examine each term in the polynomial to see if they share a common factor. If such factor exists, we remove it from the entire polynomial. Essentially, this process is just the reverse application of the distributive property. Recall that the the distributive property states that $a(b+c)=ab+ac$. In factoring out the greatest common factor we do this in reverse. We notice that each term has an $a$ in it and so we factor it out using the distributive law in reverse as follows: $ab+ac=a(b+c)$.

Let's take a look at some examples.

Factoring quadratics

XXX

The Principle of mathematical induction

Now, what is the principle of mathematical induction you might ask. The principle of mathematical induction relies on the fact that, provided we've verified that something is true (one particular instance of a proof), if we assume that the statement is true for some specific $k$ and we are able to prove that it is also true for $k+1$, then we're golden.

Why does the principle of mathematical induction work? Well, you're essentially saying that you can always prove the next iteration provided the previous one is true. We know it holds for $n = 1$ (assuming we begin the proof with $n = 1$), so it follows that it holds for $n=2$. And because it holds for $n=2$, it follows that it holds for $n = 3$. And the pattern continues, until you get to $n$.

By the way, induction proofs do not necessarily start at $n=1$. For example, $2^n > n^2$ is true for $n \geq 5$ (that is a fact, you'll work on this example soon), however it is not true for $n = 1, 2, 3, 4$), therefore its roof would start by showing it is true for $n = 5$.

And that is where the domino reference comes from.

The domino reference

Imagine dominoes lined up one after another. If you can show that:

• The first domino falls (base case), and
• Any falling domino knocks over the next domino (inductive step)

then you've shown that all dominoes will fall. Mathematical induction works similarly:

• Base case: Verify the statement is true for the first number (usually $n =1$)
• Inductive step: Assume the statement is true for an arbitrary number $n = k$ (inductive hypothesis), and then show this implies the statement must be true for the next number, $n = k+1$.

If both steps work, the statement holds for all natural numbers in the interval.

The types of induction proofs you'll need to master

Induction proofs are one of the most challenging topics in the IB curriculum for two key reasons: they involve several intricate steps (particularly in the inductive step), and there are many different types to master. As an AA HL Math student, you'll work with the following types of induction proofs:

• ✍️Induction proofs with series
• ✍️Induction proofs with divisibility
• 🔒Induction proofs with recursion
• 🔒Induction proofs with inequalities
• 🔒Induction proofs with trigonometry
• 🔒Induction proofs with differentiation
• 🔒Induction proofs with integration

Are induction proofs really that great?

A great disadvantage of the method of mathematical induction is that the formula to be proved must be known. or at least conjectured, to be true before we start. This method gives no help at all in finding the formula. However, to some extent, this is a problem with any kind of proof. There is a possible way of finding the formula to be proved. Start by working out the first few cases, then try to see a pattern, and from this conjecture what the final result should be (like we did in the beginning of this page).

FAQ on Induction proofs

Vocabulary on Induction proofs

To make sure you don't go out there calling a crocodile alligator 🐊 check the vocabulary in this topic:

🗣️Induction proofs’ vocabulary