So right now I'm working on a discrete mathematics course and I've been having a bit of trouble figuring out how to prove certain equations using mathematical induction. I have very little trouble understanding how to use mathematical induction to prove equations such as this: $1 + 2 … + n = \dfrac{n(n+1)}2$ for all integers $n \ge 1$. But when it comes to less straightforward proofs such as the one I am currently working on: "Prove that $2n + 1 \le 2^n$ for $n \ge 3$" give me real trouble. Are there any tips for proofs like this any could share? Any help is greatly appreciated.
[Math] Tips on constructing a proof by induction.
induction
Related Solutions
What is induction?
At its core, induction is this statement:
Take a set $S$. If $1 \in S$, and $k \in S$ implies that $k + 1 \in S$, then all natural numbers are in $S$.
Intuitively, this is pretty obvious. Assume both hypotheses: that $1 \in S$ and $k \in S \implies k + 1 \in S$.
- Is $1 \in S$? Yes, by assumption.
- Is $2 \in S$? Yes, because $1 \in S$, and $1 \in S$ implies $1 + 1 \in S$.
- Is $3 \in S$? Yes, because we just showed $2 \in S$, and $2 \in S$ implies $2 + 1 \in S$.
- $\ldots$
That clearly wasn't a formal proof that induction is valid, but it's a good place to start your intuition. No matter what natural number we start at, we can "step back" by one until we hit $1$, which we know is true.
Wait, how'd sets get in there?
Normally, people don't talk about sets when it comes to induction. Usually, it's about propositions. But the two are equivalent, consider the set $S = \{ n \mid P(n) \}$ or the proposition $P(n) = n \in S$. If you're working with propositions, induction is stated as:
Take a proposition $P$. If $P(1)$ is true, and $P(k)$ implies that $P(k+1)$, then $P(n)$ is true for all $n \in \mathbb{N}$.
How do we do inductive proofs?
Like any conditional statement, all you need to do is prove the two hypotheses:
- $1 \in S$ (the base case)
- If $k \in S$, then $k + 1 \in S$ (the recursive case)
or for propositions,
- $P(1)$ (the base case)
- If $P(k)$, then $P(k + 1)$ (the recursive case)
The confusing part
The recursive step sometimes confuses people. "Aren't we assuming what we want to prove?" Not quite. Here, a precise understanding of conditional statements is required. If I say, "If today is Friday, tomorrow is Saturday", I am not saying that today is Friday. I am only saying that, if we can show today is Friday, then we know tomorrow is Saturday.
It is the same with the recursive step. We are proving: "if $P$ is true for $k$, then it is also true for $k + 1$". We have not said anything about whether or not $P(k)$ is true!
Additionally, we are not assuming $P$ is true for all $k$, we are only assuming it to be true for a particular $k$. In notation, the recursive step is:
$$\forall k \in \mathbb{N} \ (P(k) \implies P(k + 1))$$
Finally, induction is not the process of proving those two statements. Those can be proved like any other statement. Induction is the statement "if those two statements are true, then $P$ is true for all natural numbers".
An example
We want to show that $\sum_{i = 1}^n i = \frac{n(n+1)}{2}$. (In terms of sets, this would be "all natural numbers are in the set $\{ n \mid \sum_{i = 1}^n i = \frac{n(n+1)}{2} \}$, but usually, the proposition syntax is easier).
"$P$ is true for $1$" is pretty easy to see, just plug it in and check.
The recursive case isn't much harder. Assume that $\sum_{i = 1}^k i = \frac{k(k + 1)}{2}$ is true for some $k$. Then, by adding $k + 1$ to both sides, we get $\sum_{i = 1}^{k+1} i = \frac{(k + 1)(k + 2)}{2}$. So, $P(k) \implies P(k+1)$.
Since $P(1)$ and $P(k) \implies P(k + 1)$, then by induction, $P(n)$ is true for all $n$.
Strong induction
The induction described above is called "weak induction". Strong induction is when your recursive hypothesis is replaced with "if $P$ is true for all $i$ less than $k$, then $P$ is true for $k$". The justification is similar, except to prove that $P(k)$ is true, we can look at any $i$ less than $k$, not just $k - 1$. It is called strong because your hypothesis is stronger, you can look at more $i$.
Sometimes this format is easier to use than weak induction. As an example, we show that all natural numbers can be written as $2^a m$, where $m$ is odd. The base case is easy, $1 = 2^0 \cdot 1$.
For the recursive case: let $k \in \mathbb{N}$ and assume that $P(i)$ is true for all $i < k$. If $k$ is odd, we are done. If not, there is some $i < k$ such that $2i = k$. By hypothesis, $i = 2^a m$ for some $a, m$, where $m$ is odd. Thus, $k = 2^{a + 1} m$.
Since $P(1)$ and $\forall i < k \ P(i) \implies P(k)$, by strong induction, $P(n)$ is true for all $n \in \mathbb{N}$. This would be difficult with weak induction.
Why is it valid?
Above, an intuitive argument for induction was shown. But in math we like to prove things. To do so, we introduce the "well-ordering principle": all non-empty subsets of $\mathbb{N}$ have a smallest element.
The well-ordering principle, weak induction, and strong induction are all equivalent!
Either you can take one of them as an axiom, or you can prove one by whichever construction of $\mathbb{N}$ you have. Then, there are pretty simple proofs to show the equivalence of the three.
Well-ordering implies weak induction: Let $S$ be a set, where $1 \in S$, and $k \in S \implies k + 1 \in S$. Let $T = \mathbb{N} \setminus S$, that is, all natural numbers not in $S$. Assume $T$ is non-empty. By well-ordering, it has a least element, $k$. Clearly it can't be $1$, because $1 \in S$. So it must be greater than $1$, and so $k - 1 \in \mathbb{N}$. Since $k$ is the smallest element in $T$, $k - 1$ can't be in $T$, meaning $k - 1 \in S$. But by assumption, that implies $(k - 1) + 1$ is in $S$, and so $k \in S$, which contradicts that $k \in T$. Therefore, $T$ was empty after all, and so $\mathbb{N} \subseteq S$.
Weak induction implies strong induction: Let $P(k)$ be a proposition where $P(1)$ and if $P(i)$ for all $i < k$, then $P(k)$. Let $Q(n)$ be the proposition "$P(k)$ is true for all $k < n$". We will use weak induction on $Q$. First, note that $Q(1)$ is true. Next, assume that $Q(n)$ is true. That means that $P(i)$ is true for all $i < k$, and so by our initial description of $P$, $P(n + 1)$ is true. But since $Q(n)$ and $P(n + 1)$ are true, $Q(n + 1)$ is true as well. Therefore, the conditions for weak induction are satisfied, and $Q(n)$ is true for all $n$. This clearly means that $P(n)$ is true for all $n$ as well.
Strong induction implies well-ordering: Let $P(n)$ be the proposition "if $n \in S$, then $S$ has a least element". Clearly it is true for $1$, because if $1 \in S$, then $1$ is the least element of $S$. For the recursive step, assume that $P(i)$ is true for all $i < k$. Then we wish to show that $P(k)$ is true. Let $k \in S$. If $k$ is the smallest element, then we are done. If not, then there is some $i < k$ such that $i \in S$. Thus, $P(i)$ is true, and so $S$ has a smallest element. By strong induction, if there is any $n \in S$, then it has a least element (this is where the "non-empty" part crops up).
Which one of these proofs you need depends on what your construction of $\mathbb{N}$ is or what axioms you have.
Write the axioms of number theory (called "Peano arithmetic," or "PA") as $P^-+\mathrm{Ind}$, where $P^-$ is the ordered semiring axioms (no induction), and $Ind$ is the axiom (scheme) of induction. Then a theorem requires some induction if it is not provable by $P^-$ alone - that is, if we can find a model of $P^-$ in which the theorem is not true.
- As an aside: the equivalence between non-provability and countermodel-existence is (the contrapositive of) Gödel's completeness theorem; see this old answer of mine for some discussion of what's going on here.
So that lets us make a precise "Question 1:"
Question 1: Is there a "natural" theorem about natural numbers which requires some induction, in the sense above?
We can refine this. Let's suppose we want to draw a line between "simple" proofs by induction, and "hard" proofs by induction; we allow the former but are skeptical about the latter.
In this case, in the same way that we broke the axioms of number theory up into parts ($P^-$ and $Ind$), we now need to break $Ind$ up into smaller pieces. The usual way of doing this is via the arithmetical hierarchy: every formula in the language of arithmetic can be assigned a "level of complexity," and these levels are indexed by natural numbers. $Ind$ can now be written as $\mathrm{Ind}_1+\mathrm{Ind}_2+ \cdots$, where $Ind_n$ is induction for formulas of complexity $n$. Roughly speaking, a formula has complexity $n$ if it can be written with $n$ alternating blocks of quantifiers: e.g., the formula $$p(a)=\text{“ }\forall x\,\forall y\,\exists z\,\forall w\,(x+y+w<z+a)\text{ ''}$$ has complexity 3, since it has the form "$\forall\forall, \exists, \forall$." (I'm being very vague here, and this is slightly incorrect; but it won't cause any problems.)
So we have question 2:
Question 2: For each $n$, are there "natural" theorems about natural numbers which require $\mathrm{Ind}_n$?
Note that if a theorem requires $\mathrm{Ind}_n$, then it certainly requires some induction; so question 2 is a strengthening of question 1. By the way, this is of course not the only way to break up $\mathrm{Ind}$; there are lots of other ways to measure the complexity of an axiom of induction.
The answers to both questions are, spectacularly, YES; the general question, "How much induction do we need to prove $\varphi$?" is studied - along with similar questions - by the field Reverse Mathematics.
Some examples:
The statement "There are infinitely many primes" is not provable in $P^-$ alone; that is, it requires some induction. How much induction exactly? I don't think this is known, but the (very weak) level of induction called open induction is known to also not be enough.
Ramsey's theorem for pairs - the statement, "Any time I color pairs of natural numbers 'Red' or 'Blue,' I can find an infinite set of natural numbers, any pair from which is colored the same as any other pair" - requires some induction. Again, exactly how much is not known, but it's at least $\mathrm{Ind}_2$ - a small but substantial amount of induction. EDIT: I'm being somewhat sloppy here. Note that Ramsey's theorem isn't expressible in the language of number theory, so I need to look at a more expressive theory which can talk about such things; the theory used for this purpose is usually $RCA_0$, which corresponds in a particularly nice way to the first level of induction + the ability to talk about sets. See Simpson's book (mentioned below) for details on this.
A lot of algebraic statements, like "Every ring which is not a field, has a nontrivial proper ideal", actually require all the induction that $PA$ has to offer.
REFERENCES
Since there's a lot of stuff here, I don't have time to give a complete explanation - but here are some sources:
For basic logic, including Gödel's completeness theorem and what a "model" is, I'm a fan of Enderton's "A Mathematical Introduction to Logic" - but there are lots of books out there on the same subject, and any of them will do.
For the arithmetical hierarchy, this will be covered in any good logic textbook, but can also be found in a lot of books on theoretical computer science - I'm pretty sure it's in Arora/Barak, for example.
For reverse mathematics, this is trickier; there isn't really any readable introduction. The classic text is Simpson's "Subsystems of Second-Order Arithmetic," and chapter I is very nice and readable, but the rest is very hard.
Best Answer
When proving inequalities by induction it’s often very helpful simply to ask yourself what happens to each side of the proposed inequality when $n$ is increased by $1$.
In this case the expression $2n+1$ on the left increases by $2$ when you replace $n$ by $n+1$, while the expression $2^n$ on the right is multiplied by $2$ when you replace $n$ by $n+1$: instead of adding $2$, you’re adding $2^n$. If $n\ge 1$, then $2^n\ge 2$, and replacing $n$ by $n+1$ adds at least as much to the righthand side as it does to the lefthand side: it adds $2^n$ to the righthand side and $2$ to the lefthand side, and $2^n\ge 2$.
At this point you’ve already essentially done the induction step: you’ve shown that if $2n+1\le 2^n$ and $n\ge 1$, then $2(n+1)+1\le 2^{n+1}$. All that remains is to find the smallest $n\ge 1$ for which $2n+1\le 2^n$, and by actual experiment that turns out to be $n=3$.