Mathematical Induction

In this lesson, we'll learn a mathematical technique called Mathematical Induction.

The mathematical induction is a mathematical proof technique. Considering that we want to prove a statement for every natural number (for example), the idea of the induction is to break our proof into steps:

• Base case: proof the statement for small cases ( for example)
• Hypothesis: suppose that the statement is true for an integer
• Induction step: proof that the statement is true for

If we can do these steps, our proof will be complete! It sounds like magic, but, in reality, it is quite simple why. We proved that our statement is valid for base cases. Considering that our base case is , by the first step, we know that the statement is valid for . By steps two and three, we can figure out that it is also valid for because, if it's valid for (step ), we know that it is valid for (step ). As it is valid for , by the same argument, it is valid for . So it's valid for too and so on.

Then, if we can complete these steps, our statement will be proved for all natural numbers. Let's see some examples of how to apply this idea in some proofs.

---

Example 1: Prove that for any

Let's prove it by mathematical induction in .

• Base case:
  • : it's true because