Perhaps you have seen the method of proof by induction before. Stated in the abstract, or exhibited in a simple example, it is easy to understand and seems hardly worth much attention. Yet induction is an extraordinarily powerful and subtle method of proof. We will use a version of induction that probably is different than what you have seen before.
Definition 2.4.1 (Induction Axiom) Suppose that $P(n)$ is a formula and $m$ and $k\ge 0$ are fixed integers. Suppose further that
1. $P(m), P(m+1),\ldots,P(m+k)$ are all true, and
2. for every $n>m+k$, the implication $P(m),\ldots,P(n-1)\Rightarrow P(n)$ is valid.
Then $P(n)$ is true for all $n\ge m$. $\square$
When $k=0$ this is often called complete induction. You may be more familiar with the simplest form of induction, where $m=1$, $k=0$, and the implication in (2) is replaced with $P(n-1)\Rightarrow P(n)$. Clearly, though, these forms of induction express the same basic idea: If some statement is true about "small'' integers, and if knowing that the statement is true up to some integer $n-1$ always allows you to prove that it is true for $n$, then the statement must be true for all $n$ (more precisely, all $n$ larger than the "small'' integers you started with). In effect, induction is a way to describe an infinite number of proofs simultaneously: how to prove $P(2)$ knowing $P(1)$, how to prove $P(3)$ knowing $P(1)$ and $P(2)$, how to prove $P(4)$ knowing $P(1)$ and $P(2)$ and $P(3)$, and so on. This only works if all the proofs are essentially the same—it is conceivable that $P(n)$ is true for all $n$, yet the proofs are much different for different values of $n$. In such an unhappy circumstance, induction will not be much help.
Proofs by induction always include verification of (1) and (2). Usually the first is called the base case or the basis of the induction, and the second is called the induction step. To prove the induction step, assume that $P(m),\ldots,P(n-1)$ are all true and try to prove $P(n)$. The statements $P(m),\ldots,P(n-1)$ are called the induction hypothesis.
Example 2.4.2 For every $n\ge 1$, $$ \sum_{i=1}^{n}i= {n(n+1)\over 2}. $$
Proof. We apply induction with $m=1$ and $k=0$ to this formula. Clearly $$ \sum_{i=1}^1i=1={1\cdot 2\over 2}, $$ proving the base case. Now, assuming that $n>1$ and $P(1),\ldots,P(n-1)$ are true, then in particular $P(n-1)$ is true, that is, $$ \sum_{i=1}^{n-1}i= {(n-1)n\over 2}, $$ so $$ \sum_{i=1}^{n}i= n+\sum_{i=1}^{n-1} i = n+ {(n-1)n\over 2} ={n(n+1)\over 2}. $$ $\qed$
This example employs the simplest kind of induction, since $k=0$ and we only needed the one case, $P(n-1)$, of the induction hypothesis. The power of the more general form is that it allows us to assume the validity of the proposition for all values less than $n$, which is very useful in many proofs.
Example 2.4.3 Every non-negative integer is either even or odd.
Proof. What we wish to establish is that every non-negative $n$ can be expressed as $2q+r$, where $r=0$ (the even case) or $r=-1$ (the odd case). We apply induction with $m=0$ and $k=1$. Clearly $0=2\cdot 0$ and $1=2\cdot1-1$. Now assume that $n\ge 2$ and that the result is true for $0, 1,…, n-1$. Then $n-2\ge 0$ so there are integers $q'$ and $r$ such that $n-2=2q'+r$, with $r=0$ or $-1$. Set $q=q'+1$; then $2q+r=2(q'+1)+r=2q'+r+2=(n-2)+2=n$, as desired.$\qed$
The following result is part of the Fundamental Theorem of Arithmetic; we will see the rest of the proof in section 3.5.
Proof. We use induction with $m=2$. Clearly $n=2$ can be factored into a product of primes (it is already prime), so the base case is true. For the induction step, assume $n>2$ and that $2,\ldots,n-1$ can each be factored into primes; we need to show that this implies that $n$ can also be factored into primes. We divide this into two cases: if $n$ is a prime, then it already is factored as desired. If $n$ is not a prime, then it factors as $a\cdot b$, where $2\le a,b< n$. Since we have assumed that all numbers between $2$ and $n-1$ factor into primes, there are primes $p_1,\ldots,p_i$ and $q_1,\ldots,q_j$ such that $a=p_1\cdots p_i$ and $b=q_1\cdots q_j$, and so $$ n=a\cdot b= p_1\cdots p_i\cdot q_1\cdots q_j, $$ that is, $n$ can be written as a product of primes.$\qed$
This proof is a very natural one, because it mimics the way most people would in fact factor a number: Faced with such a problem, you probably would try to factor the number in any way at all, writing $n=ab$. If it does not factor it must be prime and you are done. You then start over with these smaller numbers $a$ and $b$ and try to factor them. Each time you perform this operation, the factors get smaller, so you are assured that eventually the process must stop. It is possible in such circumstances to say something like this by way of proof: "Look, just keep doing this, and eventually it stops, and then the result is true.'' This is essentially proof by induction, but more informally stated. In simple cases such a proof may be acceptable, but in more difficult circumstances, it will be harder to see that such a process works. It really is best to practice doing proof by induction in the formal, "official'' manner, so that you will be prepared to write and understand more difficult proofs.
Proof. Factor $n$ into primes and grab any prime in the list.$\qed$
Exercises 2.4
Ex 2.4.1 Prove that $$ 1+3+5+\cdots +(2n-1)=n^2. $$
Ex 2.4.2 Prove that $$ 1+4+9+\cdots +n^2 = {n(n+1)(2n+1)\over 6}. $$
Ex 2.4.3 Prove that any non-negative integer can be expressed as $3q+r$, where $0\le r< 3.$
Ex 2.4.4 Prove that any $n\ge 8$ can be expressed as $3x+5y$ where $x\ge 0$ and $0\le y< 3$.
Ex 2.4.5 Suppose $a_0=1$, $a_1=2$ and for every $n>1$, $a_n=3a_{n-1}-2a_{n- 2}$. Find a simple formula for the value of $a_n$, and prove that it is correct.
Ex 2.4.6 Show that $2^{(2^n)}+1$ is a prime for $n=0,1,2,3,4$. Show that it is not prime when $n=5$. (You may use computing devices.)
Ex 2.4.7 The Fibonacci numbers are defined by $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\ge2$. Prove that $F_{m+n}=F_{m+1}F_n+F_mF_{n-1}$ for $n\ge1$ and $m\ge 0$.
Ex 2.4.8 Use the previous problem to prove that $F_n|F_{kn}$.
Ex 2.4.9 Is $n^2+n+41$ prime for every integer $n\ge 0$? If so, prove it; if not, find the smallest $n$ for which it is composite. (You may use computing devices.)
In the remaining problems, use the universe that is implied in the statement of the problem.
Ex 2.4.10 Assuming you know that the derivative of a constant is $0$ and the derivative of $x$ is $1$, use induction and the product rule to prove $(x^n)'=nx^{n-1}$ for all $n\ge 0$.
Ex 2.4.11 A polynomial is irreducible if it cannot be factored into two polynomials of strictly smaller degree. Show that any polynomial is the product of irreducible polynomials. (Hint: let $P(n)$ be the formula "all polynomials of degree $n$ can be factored into a product of irreducible polynomials''.)
Ex 2.4.12 In a round robin tennis tournament, every player plays every other player once. Let's say that a "winner'' is any player $x$ such that for every other player $y$, either $x$ beat $y$ or else there is a player $z$ such that $x$ beat $z$ and $z$ beat $y$. In a round robin tournament with at least 2 players, show there is at least one winner.
Ex 2.4.13 A polygon in the plane is convex if the segment connecting any two vertices is contained entirely inside the polygon. Use induction to prove that the sum of the $n$ angles of a convex polygon with $n$ vertices is $(n-2)\pi$. You may assume that the sum of the angles in a triangle is $\pi$.