I'm having trouble understanding why inductive proofs are logical

Question

I am new to Mathematics, reading books in my free time. I have recently learned about proving Mathematical propositions by induction. I am having a bit of trouble understanding the process and why it is logical.

I have learned that if you have a statement $A$, and you assume $A_{n}$ is true, then you can prove $A$ is true for all numbers greater than $n$ by showing that $A_{n+1}$. I don't understand this because from my point of view it looks like you only proved $A$ is true for $n$ and $n + 1$.

Maybe I am missing something, or maybe I need a formal introduction to logic. I never read anything about philosophy or logic before learning Mathematics, but if reading about logic would help me understand proofs better I would be glad to.

Answer 1

This is a duplicate of other threads on the topic on induction. However I will give you a short summary/intuitive answer:

The base case is important. We first show that $A_0$ hold, then assume that $A_n$ hold and show that this implies that $A_{n+1}$ hold.

Thus, since $n$ is any number, we may say $n=0$. We know that $A_n=A_0$ hold, but if $A_n$ hold, we have shown that A_{n+1} hold. Thus $A_{n+1}=A_{0+1}=A_1$ hold. Now do the same construction again but with $n=1$, we may now conclude that $A_{n+1}=A_2$ hold. Continue this and we will be able to show that $$A_0,A_1,A_2,A_3,A_4,\ldots$$ All hold i.e. the statement $A_n$ hold for any natural number (which I assume is the same as your statement $A$).

Answer 2

Your explanation is a bit mixed up: we assume $A_n$ and derive $A_{n+!}$, but by itself this is not enough to deduce either $A_n$ or $A_{n+1}$. What you're missing is that we need to prove $A_n \Rightarrow A_{n+1}$ for all $n$.

Suppose I want to show that the number $5$ is bigger than $1$. Since $5 = 4+1$ is bigger than $4$, we'd be done if we could show $4 > 1$ (because then $5>4 > 1$ so $5 > 1$).

But since $4 = 3+1 > 3$, we'd be done if we could show that $3 > 1$, because then $4 > 3 > 1$.

Since $3 = 2+1 > 2$, we'd be done if we could show that $2 > 1$ likewise.

But $2 = 1+1 > 1$, so we are done.

Induction captures this as a general method. If we want to show $A_n$, it is enough to show both $A_{n-1}$ and $A_{n-1} \Rightarrow A_n$; it is therefore enough to show that $A_{n-2}$ and $A_{n-2} \Rightarrow A_{n-1}$ and $A_{n-1} \Rightarrow A_n$; and so on all the way down to:

It is enough to show that $A_1$, and $A_1 \Rightarrow A_2$, and $A_2 \Rightarrow A_3$, and … and $A_{n-1} \Rightarrow A_n$.

It is therefore enough, if we want to prove $A_n$, to show that $A_1$ is true and that for every $k < n$, $A_k \Rightarrow A_{k+1}$. Or, if we want to prove that $A$ holds for all $n$, it is enough to show that $A_1$ is true and that for all $k$, $A_k \Rightarrow A_{k+1}$.

How can we do that? We must prove $A_1$, and then once we've done that, we can assume $A_k$ and attempt to prove $A_{k+1}$. This is in the same spirit as, in proving "$f(x) = 1$ implies $f(x)+1 = 2$", saying "Assume $f(x) = 1$. Then adding one to each side, $f(x)+1 = 2$, so we are done": to show $A \Rightarrow B$, it is enough to assume $A$ and prove $B$.

Answer 3

Suppose you have a statement $P(n)$, that says something about or involving the natural number $n$. The job of a mathematical induction proof is to show that $P(n)$ is true for all natural numbers. The way such a proof works is as follows.

Step 1: the base case. One must prove that $P(1)$ is true.

Step 2: the inductive case. One assumes that $P(k)$ holds for some fixed natural number $k$ and then uses this to prove that $P(k+1)$ holds.

So, why does this work? You can think of it like climbing a ladder. In step 1, we prove that we can climb the first rung of the ladder. In step 2, we prove that if we can reach the $k$th rung, then we can reach the $(k+1)$st rung as well. And this is all you need. Why? Say I want to know why $P(19)$ is true. Well, by step 1, I know that $P(1)$ is true. Then, by step 2 I get the chain $P(2)\implies P(3)\implies P(4)\implies\cdots\implies P(18)\implies P(19)$. That's pretty much the gist of it.

Answer 4

You also have to prove that it is true for some specific value of $n$. The idea is that given "$A_1$ is true" and "if any $A_n$ is true, then also $A_{n+1}$ must be true", you can conclude that every $A_n$ is true, i.e., each of $A_1,A_2, A_3,A_4,\cdots$ must be true.

It's a sort of bootstrap procedure. You combine the hypotheses to conclude $A_2$ from $A_1$, then from he newly proven $A_2$ you can conclude $A_3$, and so on indefinitely. You surely see that if you continue, you will eventually reach any given index, such as 5 or 17 or 1,000,000 ?

Answer 5

You may have misunderstood parts of the concept. One part of induction is: You prove

If $A_n$ holds, then $A_{n+1}$ holds as well.

And yo prove this implication for all values (as natural number) of $n$. So in effect you do not only prove that $A_{17}$ implies $A_{18}$, but all at once also that $A_{42}$ implies $A_{43}$ and that $A_{1729}$ implies $A_{1730}$ and ...

There is just one last (or in a sense first) step missing that you did not mention: One needs to explicitly prove $A_0$ (or $A_1$, depending on where you start counting). Once this is done, $A_0$ implies $A_1$, which implies $A_2$, which implies $A_3$, which implies $A_4$, and so on. For any natural number $n$ this "and so on" will prove $A_n$ after finitely many steps. This last observation may seem unfounded, but it is in fact the very property we ascribe to the concept of natural number.

Answer 6

As others have noted, you’ve somewhat misunderstood the mechanics of a proof by induction. Say that we want to use induction to prove that some statement $P(n)$ about integers $n$ is true for all positive integers.

• We verify that $P(1)$ is true.
• We then prove that if $P(n)$ is true for some (unspecified) $n$, then $P(n+1)$ must necessarily be true. At this point we’re not actually claiming that $P(n)$ is true: we’re just proving that if that should happen to be the case, then $P(n+1)$ will also be true.

If we can do both of these things, we’re entitled to conclude that $P(n)$ is true for all integers $n\ge 1$.

One nice way to see why this works is to imagine that we’ve carried out both parts of the proof by induction, and yet the result is false: there is at least one integer $n\ge 1$ such that $P(n)$ is not true. In that case we can let $B=\{n\ge 1:P(n)\text{ is not true}\}$, the set of ‘bad’ positive integers. This is then a non-empty set of positive integers, so it has a smallest member; call that member $m$. (It’s a basic fact about the positive integers that every non-empty set of them has a smallest member.)

Now what can $m$ be? It can’t be $1$, because $P(m)$ isn’t true, and we checked that $P(1)$ is true. Thus, $m>1$, and $m-1$ is therefore a positive integer. Moreover, $m-1$ is smaller than $m$, which is the smallest member of $B$, so $m-1\notin B$, and therefore $P(m-1)$ is true. But we showed that if $P(m-1)$ is true for any given integer $m-1$, then $P\big((m-1)+1\big)=P(m)$ is also true. We now have a contradiction: on the one hand $m\in B$, so $P(m)$ is false, but on the other hand $m-1\notin B$, so $P(m-1)$ is true, and therefore by the second part of our proof $P(m)$ is true.

The only way out is to conclude that no such $m$ exists, which means that the set $B$ of bad positive integers must not have had a smallest member. This is possible only if $B$ is empty, meaning that there are no ‘bad’ positive integers: $P(n)$ is actually true for all positive integers.

This way of thinking about it avoids the imagery of climbing a ladder or having one domino knock over the next and allows you to think of the proof as a single event, not some kind of iterative process.

Answer 7

Pierre de Fermat called it "infinite descent". The natural numbers are well-ordered, which is short for saying that if there is a natural number with property $P$, there is a LEAST one with property P.

So suppose $\neg A_n$ means "$n$ has property $P.$" So if $\neg A_n$ is true for any $n$, then there is a least $k$ such that $\neg A_k.$

But if $A_1$ is true, and if $A_n\implies A_{n+1}$ is true for ANY $n$, there can't be any such $k.$ Because $A_{k-1}$ is true and $A_{k-1}\implies A_k.$