Mathematical induction

Imagine a line of dominoes stretching out forever.

If you knock down the first one, it hits the second. The second hits the third, and so on. This creates a chain reaction that never stops. In math, we use a similar idea called mathematical induction. It is a way to prove a statement is true for every natural number. A natural number is a whole number like 1, 2, or 3. This method helps us check infinitely many cases using just a few steps. It turns a huge job into a simple, logical chain.

To use this method, you must complete two specific steps. The first is called the base case. You prove the idea works for the very first number, which is often 0 or 1. The second step is the induction step. Here, you assume the idea works for a number called "n." This assumption is called the induction hypothesis. Then, you must prove that if it works for "n," it must also work for the next number, "n plus one."

If both steps are true, the idea must be true for every number in the chain.

Many thinkers used this idea throughout history. Around 1000 AD, a Persian mathematician named al-Karaji used it for arithmetic sequences. He applied it to things like Pascal's triangle. Later, in 1575, Francesco Maurolico used it to study odd integers. In 1665, Blaise Pascal wrote about math patterns using this technique. Another Frenchman named Fermat used a related idea called infinite descent. Eventually, the method became very famous thanks to thinkers like Jakob Bernoulli. It was a way to build certain truth through logic.

Mathematical induction is very different from how people use the word "induction" in philosophy. In philosophy, people look at many cases to guess a probable answer. In math, induction provides a rigorous, certain proof. It is not just a guess about what might happen. Instead, it uses a finite chain of reasoning to cover infinite values. This makes it a foundational tool in modern math and logic. It is even used to check if computer programs are correct. Experts rely on it to ensure that code works exactly as intended.

This method can also change to fit different puzzles. Sometimes, you might not start at 1. You could prove something is true for all numbers starting at 10. You can even use it on more than one number at a time. There is also a version called structural induction. This works on things like trees in computer science. It is closely related to a concept called recursion. Whether it is used for simple numbers or complex shapes, induction helps us find the truth in patterns.