# Proving Theorems

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.

• Induction is not a definition. It is one of Peano's axioms. – Hetebrij Oct 8 '15 at 19:03
• You can try with Daniel J.Velleman, How to Prove It : A Structured Approach (2006). – Mauro ALLEGRANZA Oct 8 '15 at 19:03
• Look into this book: Set Theory and the Continuum Hypothesis. Despite the "scary" title, the book starts from the absolute basics. Also, the reason induction "works" is more a consequence of how the natural numbers are defined rather than a general mathematical truth. The book does a good job of explaining this. – 0XLR Oct 8 '15 at 19:06
• @ZeroXLR: The book you link to is called Set Theory and the Continuum Problem. On the other hand, the title you quote is that of Cohen's deeply technical monograph about forcing and why ZFC does not prove the continuum hypothesis -- which is certainly not something that can be recommended to a beginner. – Henning Makholm Oct 8 '15 at 19:55
• You can see also : Ethan Bloch, Proofs and Fundamentals : A First Course in Abstract Mathematics (2nd ed - 2011). – Mauro ALLEGRANZA Oct 8 '15 at 20:33

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.

• In most "actual" contexts, induction is not an axiom. It is a true statement about the naturals, and follows from the naturals being a well-ordered set in which each element apart from the smallest has an immediate predecessor. I put actual in quotes because of course sometimes people do work in PA or similar. – Tobias Kildetoft Oct 8 '15 at 19:22
• Thanks for this. I would have said so sooner, but I'm very new and just reached 50 rep a few minutes ago. – Algebraic Oct 8 '15 at 21:08

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".

• But you really cannot do induction "down" in order to prove anything about all naturals (unless you can prove it for arbitrarily large initial values). – Tobias Kildetoft Oct 8 '15 at 19:58
• Obviosly! However if you find P is true for a large n (which can happen) it is not in any way true for all n excepting you apply induction "down". – Piquito Oct 8 '15 at 20:11
• @Mr Downvote: One day an user (I let you imagine why not give the exact reference) having about 8000 of reputation, wrote this comment to me: “don't be ridiculous. How on earth can you prove the series of prime number reciprocals is divergent without already knowing that there is an infinitude of prime numbers? “ My reply was : “If any ridiculous in this story, not me but Euler. Take it easy and breathe deeply”. It is not impossible your in-depth knowledge on the induction principle would be imperfect. – Piquito Oct 9 '15 at 14:35