Proving Theorems

Question

I've been struggling with the concept of proofs ever since I completed my introductory logic course "Axiomatic Systems". In that course it seemed to be easy. We were pretty much just using various logical methods to prove the properties of real numbers. Now it doesn't seem nearly as simple. I often find myself stumped when my real analysis text claims "by the principle of mathematical induction this is true," offering no evidence whatsoever that the PMI implies anything. This makes me believe that I must not understand basic concepts like that very well. I really need a reference that properly explains these concepts to me, because even looking through my old axiomatic book I see no clear definition of induction. I'm not sure why I expected a good answer from that book. How could I when our assigned text was just over 70 pages for a full semester? (70 pages WITH examples in case you were wondering)

An explanation of mathematical induction would be appreciated, but I really would prefer book recommendations.

Answer 1

Induction is, in essence, a way of proving statements about integers. The "fact" that it works is really an axiom, and it says:

If $P(n)$ is some property of natural number $n$ which satisfies the following conditions:

1. $P(1)$ is true.
2. $P(n)\implies P(n+1)$ is true. Then the statement $$\forall n\in\mathbb N: P(n)$$ is also true.

In practice, you prove statements by induction in two steps. For example, let's have a look at how you can prove that $$2^0 + 2^1 + \dots + 2^n = 2^{n+1} - 1$$

In the first step, you prove that the statement is true if $n=1$. Therefore, you prove that $2^0 + 2^1 = 2^{1+1} -1$ which is trivial to prove.

In the second step, we assume that the statement is true for some $n$. Then, we try to prove that from this assumption, it follows that the statement is true for $n+1$. In our case, we assume that $$2^0 + 2^1 + \dots + 2^n = 2^{n+1} - 1$$ and we want to prove that

$$2^0 + 2^1 + \dots + 2^{n+1} = 2^{(n+1) + 1} - 1$$

This step is where mathematical creativity comes in. There is no blueprint to what you do next.

In our case, we prove it like this:

We know that $$2^0 + 2^1 + \dots + 2^n = 2^{n+1} - 1$$

But that means that $$2^0 + 2^1 + \dots + 2^{n+1} =\\ \left(2^0 + 2^1 +\dots + 2^n\right) + 2^{n+1} =\\ \left(2^{n+1} - 1\right) + 2^{n+1} =\\ 2\cdot 2^{n+1} -1 = 2^{n+1+1} - 1 = 2^{(n+1) +1} -1$$

which proves our equality.

Answer 2

If you want to really understand its full significance the principle of induction you should, in particular, not overlook that you can also show that if true for n also should apply to n-1 (not for "up" but for "down").

This is a modality that goes unnoticed by many people.

I recommend the Godement's book Cours d'Algèbre in its first six chapters and see in the fifth "Le raissonement par recurrence".