# Why does induction prove equality?

I know how to prove equality for my homework assignment, but I can't understand why it actually proves that equality. Could you please explain?

-
You would have to provide more detail for anyone to be able to explain. I also suggest softening the title, since it's unnecessary and bound to rankle somebody. – Dylan Moreland May 26 '12 at 21:01
@DylanMoreland: I just want to understand why induction proves equality like 1+2+3... n = n(n+1)/2 and so on... I don't know what else to write? Sorry – hey May 26 '12 at 21:03
That example is a good start. – Dylan Moreland May 26 '12 at 21:04
Induction does not prove equality per se. Induction is a way of proving infinitely many statements (one for each positive integer) without having to establish each of them separately. These statements need not be in the form of an equality. Maybe you can start with this question. – Arturo Magidin May 26 '12 at 21:09

The idea behind induction is to prove a claim about all natural numbers. The induction is just a process which allows us to step through all the cases "at once".

Let us consider the following statement: $$1+\ldots+n = \frac{n(n+1)}2$$

We can view this as a statement that says:

for a natural number $n$, the sum of $1+\ldots+n$ is exactly $\frac{n(n+1)}2$.

We claim that this is true for every natural number.

However checking an infinite list of numbers for whether or not the equality holds for each one is quite an arduous and time consuming task (and just think of all the draft papers you will have to use...).

Instead what we do is argue the following logical steps:

• We verify the claim is true for $n=1$, that is we verify that $1=\frac{1\cdot(1+1)}2=1$.
• Suppose now that the claim was true for some natural number $n$, from this assumption we prove it for $n+1$.

If the claim was not true for all natural numbers then there would be a first number for which is it not true. At that point the step from $n$ to $n+1$ would have to fail (if we do things properly, that is).

What happened here is that we made some sort of a meta-proof, a mold for a proof. Now you can ask me "okay, show me the claim is true for $500$." and I will argue that the induction step tells me that if $499$ has the property, then so does $500$; and if $498$ has it then so does $499$ and therefore $500$ too. I will continue this decreasing argument until I reach $1$. Then I will say: "Okay, but we verified that $1$ indeed has the wanted property, therefore $2$ has it and therefore $3$ has it, and so on...", until $500$. This holds mathematically because we make finitely many arguments. This finite number may be very large, but hey... most numbers are larger.

So what we prove is not the equality itself, but rather that the equality is true for every natural number.

-
Arduous, time consuming, and all the draft papers.... This one has me cracking up, Asaf! – Cameron Buie May 26 '12 at 21:29

Let's say you have the following formula that you want to prove:

$$\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}$$

This formula provides a closed form for the sum of all integers between $1$ and $n$.

We will start by proving the formula for the simple base case of $n = 1$. In this case, both sides of the formula reduce to $1$. This means that the formula holds for $n = 1$.

Next, we will prove that: If the formula holds for a value $n$, then it also holds for the next value of $n$ (or $n + 1$). In other words, if the following is true:

$$\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}$$

Then the following is also true:

$$\sum_{k=1}^{n+1} k = \frac{(n + 1)(n + 2)}{2}$$

To do so, let's start with the first side of the last formula:

$$s_1 = \sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n + 1)$$

That is, the sum of all integers between $1$ and $n + 1$ is equal to the sum of integers between $1$ and $n$, plus the last term $n + 1$.

Since we are basing this proof on the condition that the formula holds for $n$, we can write:

$$s_1 = \frac{n(n + 1)}{2} + (n + 1) = \frac{(n + 1)(n + 2)}{2} = s_2$$

As you can see, we have arrived at the second side of the formula we are trying to prove, which means that the formula does indeed hold.

This finishes the inductive proof, but what does it actually mean?

1. The formula is correct for $n = 1$.
2. If the formula is correct for $n$, then it is correct for $n + 1$.

From 1 and 2, we can say: If the formula is correct for $n = 1$, then it is correct for $n + 1 = 1 + 1 = 2$. Since we proved the case of $n = 1$ at the beginning, then the case of $n = 2$ is indeed correct.

We can repeat this above process again. The case of $n = 2$ is correct, then the case of $n = 3$ is also correct. This process can go ad infinitum; the formula is correct for all integer values of $n \ge 1$.

-

Assume that all $\emptyset \neq B \subset \mathbb{N}$ has the smallest element $n_0$. Let $X =\{ n \in \mathbb{N}: P(n) \ \mbox{is true}\}$($P$ of property). Hence if $$(1) \quad P(n_0) \quad \mbox{is true.}$$

and $$(2) \quad P(n) \Rightarrow P(n+1)$$ Then $X \supset \{n \in \mathbb{N}:n \ge n_0\}$. In fact, by (1) $n_0 \in X$. If $X\neq\{n \in \mathbb{N}:n \ge n_0\}$ there exist $n_1$ the smallest element of $\mathbb{N} - X$ because $\emptyset \neq X \subset \mathbb{N}$. Then $n_{1} - 1 \in X$ and by (2) we have $n_1 \in X$. Contradiction. Consider now $P(n)$ is true if $$(3) \quad \sum_{k=1}^{n}k = \dfrac{n(n+1)}{2}.$$ As $P(1)$ is true and (2) holds, $X=\mathbb{N}$ and (3) hold for all $n \in \mathbb{N}$.

-
Your wording seems strange to me. What's $B$? – Ben Millwood May 26 '12 at 22:22
To get really formal, the $\sum(n, f)$ function should also be defined by induction on $n$, and this definition used in the proof. – marty cohen May 27 '12 at 0:44