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