How can you prove a statement is true for every single natural number? You can't test them one by one, since there are infinitely many. This is where mathematical induction comes in. It's a powerful proof technique that works like a line of dominoes: if you can prove the first domino will fall, and you can prove that any falling domino will knock over the next one, you've proven the entire line will fall.

In mathematics, our "statement" is a proposition that depends on an integer $n$. We often write this as $P(n)$. For example, we might want to prove that the sum of the first $n$ positive integers is given by the formula:

$P(n): 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$

Induction provides the logical framework to prove this statement holds for all $n \ge 1$.

A formal proof by induction has three distinct parts. Each one is essential for the logic to hold.

Let's start with the base case. This is your starting point, the act of tipping the very first domino. If you can't prove $P(1)$ is true, the whole chain reaction fails before it even begins. For our example, we test the formula with $n=1$.

With the base case established, we move to the core of the argument. We first make an assumption, known as the Inductive Hypothesis. We don't know if $P(k)$ is true for all k, but we assume it's true for one specific, arbitrary integer $k \ge 1$. This is like assuming an arbitrary domino, the $k^{th}$ one, falls.

Now for the Inductive Step. This is where we prove the chain reaction works. We must show that the truth of $P(k)$ logically forces the truth of $P(k+1)$. In other words, we must prove that if domino $k$ falls, it must knock over domino $k+1$. Let's write out what we need to prove, which is the statement $P(k+1)$:

To start the proof, we'll begin with the left side of the $P(k+1)$ equation and use algebra to show it equals the right side. The key move is to find a way to use our Inductive Hypothesis.

By successfully completing all three steps, we have created a rigorous logical argument. We proved the first domino falls (Base Case). Then we proved that any falling domino necessarily knocks over the next one (Inductive Step). The conclusion is that all dominoes must fall.

When writing a formal proof for an exam, you must clearly state each part: the proposition $P(n)$, the base case verification, the inductive hypothesis, the algebraic steps of the inductive step, and a final concluding statement. The reasoning of Euclid in ancient Greece contained early forms of this inductive logic.

Your concluding statement should summarize what you've accomplished.

Conclusion: We have shown that $P(1)$ is true, and we have shown that if $P(k)$ is true for some integer $k \ge 1$, then $P(k+1)$ is also true. Therefore, by the principle of mathematical induction, the statement $P(n)$ is true for all integers $n \ge 1$.