A.2 Induction and well-ordering

Most proofs about “all $𝑛$ ” in this book are inductions, and the measure $𝑛$ is rarely the obvious one: it is the length of a list, the size of a matrix, the degree of a polynomial, the number of points a permutation moves, or the dimension of a space. This section states the three equivalent forms of induction and proves that they are equivalent, then discusses how induction is set up in linear algebra, where the induction hypothesis is usually applied to a different space from the one we started with.

A.2.1Three forms of induction

Theorem A.2.1 (Induction, strong induction, and well-ordering). For each integer $𝑛 \geq 0$ let $𝑃 (𝑛)$ be a statement. The following three principles are equivalent.

(I)(Induction.) If $𝑃 (0)$ holds, and $𝑃 (𝑛)$ implies $𝑃 (𝑛 + 1)$ for every $𝑛 \geq 0$ , then $𝑃 (𝑛)$ holds for every $𝑛 \geq 0$ .
(II)(Strong induction.) If, for every $𝑛 \geq 0$ , the truth of $𝑃 (𝑘)$ for all $0 \leq 𝑘 < 𝑛$ implies $𝑃 (𝑛)$ , then $𝑃 (𝑛)$ holds for every $𝑛 \geq 0$ .
(III)(Well-ordering.) Every nonempty subset of $ℕ$ has a least element.

“Equivalent” means that each principle can be derived from each other one, using only the arithmetic and order of the integers (every $𝑛 \geq 1$ is $𝑘 + 1$ for some $𝑘 \geq 0$ , and $𝑘 < 𝑛 + 1$ if and only if $𝑘 \leq 𝑛$ ). One of them has to be taken as an axiom about $ℕ$ ; the usual choice is (I), one of Peano’s axioms for the natural numbers. So all three are true, and we use whichever is convenient. Technique 5.2.12 describes when strong induction and well-ordering are the convenient forms. Here we prove that they are no stronger than ordinary induction.

Intuition. Strong induction looks stronger than induction, because its hypothesis assumes more. The trick in (I)

\Rightarrow

(II) is to induct on the statement “

𝑃 (0), \dots, 𝑃 (𝑛)

all hold”, whose single predecessor is the whole history. Well-ordering is strong induction in contrapositive form: a set with no least element cannot contain

0

, then cannot contain

1

, and so on, and strong induction makes “and so on” precise.

Proof.standard

Uses. the order of the integers

Techniques. Proving TFAE (Technique 2.7.1), Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Prove (I)

\Rightarrow

(II)

\Rightarrow

(III)

\Rightarrow

(I). For the first, apply (I) to a different statement

𝑄 (𝑛)

that packages

𝑃 (0), \dots, 𝑃 (𝑛)

together.

Hint 2. For (II)

\Rightarrow

(III), take

𝑆 \subseteq ℕ

with no least element and prove “

𝑛 \notin 𝑆

” for all

𝑛

by strong induction.

Hint 3. For (III)

\Rightarrow

(I), look at the set of

𝑛

for which

𝑃 (𝑛)

fails, and at its least element

𝑚

. Why is

𝑚 \neq 0

, and what about

𝑚 - 1

Sketch. (I)

\Rightarrow

(II): apply induction to

𝑄 (𝑛)

: “

𝑃 (𝑘)

for all

𝑘 \leq 𝑛

”. (II)

\Rightarrow

(III): if

𝑆

has no least element, then

𝑛 \notin 𝑆

whenever no

𝑘 < 𝑛

is in

𝑆

(else

𝑛

would be least), so

𝑆 = \emptyset

by strong induction. (III)

\Rightarrow

(I): a least counterexample

𝑚

is not

0

, and

𝑃 (𝑚 - 1)

holds by minimality, so

𝑃 (𝑚)

holds, a contradiction.

We prove (I) $\Rightarrow$ (II) $\Rightarrow$ (III) $\Rightarrow$ (I).

(I) $\Rightarrow$ (II). Assume the hypothesis of (II), and let $𝑄 (𝑛)$ be the statement “ $𝑃 (𝑘)$ holds for all $0 \leq 𝑘 \leq 𝑛$ ”. The hypothesis of (II) for $𝑛 = 0$ has an empty premise, since there is no $𝑘$ with $0 \leq 𝑘 < 0$ ; so $𝑃 (0)$ holds, which is $𝑄 (0)$ . If $𝑄 (𝑛)$ holds, then $𝑃 (𝑘)$ holds for all $𝑘 < 𝑛 + 1$ , so the hypothesis of (II) gives $𝑃 (𝑛 + 1)$ , and $𝑄 (𝑛 + 1)$ follows. By (I), $𝑄 (𝑛)$ holds for all $𝑛$ , and in particular so does $𝑃 (𝑛)$ .

(II) $\Rightarrow$ (III). Let $𝑆 \subseteq ℕ$ have no least element. We show by strong induction that $𝑃 (𝑛)$ : “ $𝑛 \notin 𝑆$ ” holds for every $𝑛$ , so that $𝑆 = \emptyset$ . Suppose $𝑘 \notin 𝑆$ for all $𝑘 < 𝑛$ . If $𝑛$ were in $𝑆$ , then every element $𝑠 \in 𝑆$ would satisfy $𝑠 \geq 𝑛$ (as $𝑠 < 𝑛$ would give $𝑠 \notin 𝑆$ ), so $𝑛$ would be the least element of $𝑆$ . Hence $𝑛 \notin 𝑆$ . By (II), $𝑆 = \emptyset$ , which is the contrapositive of (III).

(III) $\Rightarrow$ (I). Assume the hypotheses of (I), and suppose for contradiction that $𝑆 =$ ${𝑛 \in ℕ | 𝑃 (𝑛) fails}$ is nonempty. By (III) it has a least element $𝑚$ . Since $𝑃 (0)$ holds, $𝑚 \geq 1$ , so $𝑚 - 1 \in ℕ$ , and $𝑚 - 1 \notin 𝑆$ because $𝑚 - 1 < 𝑚$ . So $𝑃 (𝑚 - 1)$ holds, and the hypothesis of (I) gives $𝑃 (𝑚)$ , contradicting $𝑚 \in 𝑆$ . □

Induction can start at any integer $𝑛_{0}$ : to prove $𝑃 (𝑛)$ for all $𝑛 \geq 𝑛_{0}$ , apply Theorem A.2.1 to the statements $𝑃 (𝑛_{0} + 𝑛)$ , $𝑛 \geq 0$ . Likewise, every nonempty set of integers that are all $\geq 𝑛_{0}$ has a least element.

Example A.2.2 (A geometric sum of matrices). For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and every $𝑘 \geq 1$ ,

(𝐼 - 𝐴) (𝐼 + 𝐴 + 𝐴^{2} + \dots + 𝐴^{𝑘 - 1}) = 𝐼 - 𝐴^{𝑘} .

For $𝑘 = 1$ both sides are $𝐼 - 𝐴$ . If the identity holds for $𝑘$ , then by distributivity

\begin{aligned} (𝐼 - 𝐴) (𝐼 + 𝐴 + \dots + 𝐴^{𝑘}) & = (𝐼 - 𝐴) (𝐼 + 𝐴 + \dots + 𝐴^{𝑘 - 1}) + (𝐼 - 𝐴) 𝐴^{𝑘} \\ = 𝐼 - 𝐴^{𝑘} + 𝐴^{𝑘} - 𝐴^{𝑘 + 1} = 𝐼 - 𝐴^{𝑘 + 1}, \end{aligned}

so it holds for $𝑘 + 1$ . In particular, if $𝐴^{𝑘} = 0$ for some $𝑘$ , then $𝐼 - 𝐴$ is invertible, with inverse $𝐼 + 𝐴 + \dots + 𝐴^{𝑘 - 1}$ (the other product equals $𝐼$ by the same computation, or by Theorem 3.5.23).

Example A.2.3 (Factorization into primes). Every integer $𝑛 \geq 2$ is a product of primes (a prime counts as a product of one prime). We use strong induction, starting at $2$ . Let $𝑛 \geq 2$ and suppose every $𝑘$ with $2 \leq 𝑘 < 𝑛$ is a product of primes. If $𝑛$ is prime, we are done. Otherwise $𝑛 = 𝑎 𝑏$ with $2 \leq 𝑎, 𝑏 < 𝑛$ , and $𝑎$ and $𝑏$ are products of primes by hypothesis, hence so is $𝑛$ .

Ordinary induction would be awkward here: the factors $𝑎$ and $𝑏$ are smaller than $𝑛$ , but we cannot say by how much, so knowing $𝑃 (𝑛 - 1)$ alone does not help.

The well-ordering principle is the form to use when an argument begins “take the least $𝑛$ such that $\dots$ ”. The book needs it once in an essential way, already in Definition 1.1.19: dividing integers with remainder.

Proposition A.2.4 (Division with remainder). Let

𝑛 \geq 1

and

𝑥 \in ℤ

. There are unique integers

𝑞

and

𝑟

with

𝑥 = 𝑞 𝑛 + 𝑟

and

0 \leq 𝑟 < 𝑛

Proof.routine

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9), Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Among the numbers

𝑥 - 𝑞 𝑛

with

𝑞 \in ℤ

, look at the nonnegative ones, and take the least.

Hint 2. Why is the set of nonnegative values of

𝑥 - 𝑞 𝑛

nonempty? Try

𝑞 = - | 𝑥 |

Hint 3. If the least one,

𝑟 = 𝑥 - 𝑞 𝑛

, satisfied

𝑟 \geq 𝑛

, then

𝑥 - (𝑞 + 1) 𝑛

would be smaller. For uniqueness, if

𝑞 𝑛 + 𝑟 = 𝑞^{'} 𝑛 + 𝑟^{'}

, then

𝑛

divides

𝑟 - 𝑟^{'}

, and

| 𝑟 - 𝑟^{'} | < 𝑛

Sketch. Let

𝑆 =

{𝑥 - 𝑞 𝑛 | 𝑞 \in ℤ} \cap

ℕ

. It contains

𝑥 + | 𝑥 | 𝑛 \geq 0

, so it has a least element

𝑟 = 𝑥 - 𝑞 𝑛

. If

𝑟 \geq 𝑛

, then

𝑟 - 𝑛 \in 𝑆

is smaller, so

0 \leq 𝑟 < 𝑛

. If

𝑞 𝑛 + 𝑟 = 𝑞^{'} 𝑛 + 𝑟^{'}

with

0 \leq 𝑟, 𝑟^{'} < 𝑛

, then

(𝑞 - 𝑞^{'}) 𝑛 = 𝑟^{'} - 𝑟

has absolute value less than

𝑛

, so it is

0

Existence. Let $𝑆 =$ ${𝑥 - 𝑞 𝑛 | 𝑞 \in ℤ and 𝑥 - 𝑞 𝑛 \geq 0} \subseteq$ $ℕ$ . Taking $𝑞 = - | 𝑥 |$ gives $𝑥 +$ $| 𝑥 | 𝑛 \geq$ $𝑥 +$ $| 𝑥 | \geq$ $0$ , so $𝑆$ is nonempty, and by well-ordering (Theorem A.2.1(III)) it has a least element $𝑟 = 𝑥 - 𝑞 𝑛$ . Then $𝑟 \geq 0$ . If $𝑟 \geq 𝑛$ , then $𝑥 -$ $(𝑞 + 1) 𝑛 =$ $𝑟 -$ $𝑛 \geq$ $0$ is an element of $𝑆$ smaller than $𝑟$ , which is impossible. So $0 \leq 𝑟 < 𝑛$ .

Uniqueness. If $𝑥 =$ $𝑞 𝑛 +$ $𝑟 =$ $𝑞^{'} 𝑛 +$ $𝑟^{'}$ with $0 \leq 𝑟, 𝑟^{'} < 𝑛$ , then $(𝑞 - 𝑞^{'}) 𝑛 = 𝑟^{'} - 𝑟$ , and $- 𝑛 <$ $𝑟^{'} -$ $𝑟 <$ $𝑛$ . A multiple of $𝑛$ strictly between $- 𝑛$ and $𝑛$ is $0$ , so $𝑞 = 𝑞^{'}$ and $𝑟 = 𝑟^{'}$ . □

The remainder $𝑟$ is the number $𝑥 mod 𝑛$ of Definition 1.1.19. The polynomial version, Theorem 7.1.14, has the same shape: there the size of a remainder is its degree, and the proof uses strong induction on the degree.

A.2.2Induction in linear algebra

An induction proof has three parts, and in linear algebra each of them needs a decision.

The first is the measure: the quantity $𝑛$ that the induction runs on. In this book it is the length of a list (Technique 1.6.9, as in Theorem 1.6.10 and Lemma 4.1.2), the number of summands in a direct sum (Technique 4.4.10), the size of a matrix (Technique 5.5.17, as in cofactor expansion), the number of points a permutation moves or the degree of a polynomial (Technique 5.2.12), and the dimension of a space (in Section 7.5 and Section 8.2). The right measure is one that a natural reduction step makes smaller.

The second is the statement $𝑃 (𝑛)$ , and here linear algebra has a characteristic feature. In an induction on dimension, the reduction step replaces $𝑉$ by a smaller space: an invariant subspace, a complement, or a quotient. So the induction hypothesis must apply to every space of smaller dimension, not just to subspaces of the original one, and $𝑃 (𝑛)$ has to be quantified accordingly: “for every vector space $𝑉$ with $dim 𝑉 = 𝑛$ and every $𝑇 \in L (𝑉)$ with the stated properties, the conclusion holds”. The hypothesis is then applied to some $𝑇^{'} \in L (𝑉^{'})$ built from $𝑇$ , for instance the restriction of $𝑇$ to an invariant subspace (Definition 7.2.1). This $𝑇^{'}$ must again be an operator on $𝑉^{'}$ , which is the point that Exercise A.2.13 gets wrong. Similarly, an induction on the length of a list proves a statement about every list of length $𝑛$ in every space, so that it can be applied to a shorter list after a vector has been removed or replaced.

The third is the base case, which is often $𝑛 = 0$ (the empty list, the zero space) or $𝑛 = 1$ . The base case has to be checked (Exercise A.2.12), and the step from $𝑛$ to $𝑛 + 1$ must be valid for every $𝑛$ at or above the base case, including the smallest one. The classic false proof that any $𝑛$ objects are equal breaks exactly there: its step works for $𝑛 \geq 2$ but not from $𝑛 = 1$ to $𝑛 = 2$ .

Sometimes the statement we want is too weak to prove by induction directly: the hypothesis $𝑃 (𝑛)$ does not give enough to prove $𝑃 (𝑛 + 1)$ . Then the fix is often to prove more.

Technique A.2.5 (Strengthen the induction hypothesis). If the induction step fails because $𝑃 (𝑛)$ is too weak to imply $𝑃 (𝑛 + 1)$ , replace $𝑃 (𝑛)$ by a stronger statement $𝑃^{'} (𝑛)$ that implies it and that does carry from $𝑛$ to $𝑛 + 1$ . The stronger statement is harder to prove, but the hypothesis you get to use is stronger too, and often the step becomes easy.

Reach for it when an induction step needs information about the smaller case that $𝑃 (𝑛)$ does not record. Typical strengthenings: replace a bound by a sharper one that depends on $𝑛$ ; carry along an extra property of the object being built, as Gram–Schmidt carries the equality of the spans of the first $𝑘$ inputs and outputs (Section 6.4); or prove a statement for all objects of size $𝑛$ rather than for one. The canonical example is Example A.2.6.

Used in 1 place

Exercise A.2.11.

Example A.2.6 (A bound that has to be sharpened). We show that $\sum_{𝑘 = 1}^{𝑛} 1 / 𝑘^{2} < 2$ for all $𝑛 \geq 1$ . Induction on “ $𝑆_{𝑛} =$ $\sum_{𝑘 = 1}^{𝑛} 1 / 𝑘^{2} <$ $2$ ” fails: from $𝑆_{𝑛} < 2$ we only get $𝑆_{𝑛 + 1} <$ $2 +$ $1 / {(𝑛 + 1)}^{2}$ . The trouble is that the hypothesis leaves no room for the next term. So we prove the stronger statement

𝑆_{𝑛} \leq 2 - \frac{1}{𝑛} for all 𝑛 \geq 1 .

For $𝑛 = 1$ , $𝑆_{1} = 1 = 2 - 1$ . If $𝑆_{𝑛} \leq 2 - 1 / 𝑛$ , then

𝑆_{𝑛 + 1} \leq 2 - \frac{1}{𝑛} + \frac{1}{{(𝑛 + 1)}^{2}} \leq 2 - \frac{1}{𝑛} + \frac{1}{𝑛 (𝑛 + 1)} = 2 - \frac{1}{𝑛 + 1},

using $1 / 𝑛 -$ $1 / (𝑛 + 1) =$ $1 / (𝑛 (𝑛 + 1))$ . Hence $𝑆_{𝑛} \leq 2 - 1 / 𝑛 < 2$ for every $𝑛$ .

Exercises

Exercise A.2.7.routine Let

𝜆 \in 𝐹

and

𝐽 = (\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix})

. Show that

𝐽^{𝑛} =

(\begin{matrix} 𝜆^{𝑛} & 𝑛 𝜆^{𝑛 - 1} \\ 0 & 𝜆^{𝑛} \end{matrix})

for every

𝑛 \geq 1

, where

𝑛 𝜆^{𝑛 - 1}

means

𝜆^{𝑛 - 1}

added to itself

𝑛

times.

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering), Definition 2.4.1 (Matrix product)

Hint 1. Induct on

𝑛

. Write

𝐽^{𝑛 + 1} = 𝐽^{𝑛} 𝐽

Hint 2. Multiply out

(\begin{matrix} 𝜆^{𝑛} & 𝑛 𝜆^{𝑛 - 1} \\ 0 & 𝜆^{𝑛} \end{matrix}) (\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix})

; the top right entry is

𝜆^{𝑛} + 𝑛 𝜆^{𝑛}

Sketch. For

𝑛 = 1

the formula reads

𝐽

. If it holds for

𝑛

, then

𝐽^{𝑛 + 1} = 𝐽^{𝑛} 𝐽

has entries

𝜆^{𝑛 + 1}

𝜆^{𝑛} +

𝑛 𝜆^{𝑛 - 1} 𝜆 =

(𝑛 + 1) 𝜆^{𝑛}

0

𝜆^{𝑛 + 1}

For $𝑛 = 1$ the right side is $(\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix}) = 𝐽$ , since $1 𝜆^{0} = 1$ . Suppose the formula holds for some $𝑛 \geq 1$ . Then

𝐽^{𝑛 + 1} = 𝐽^{𝑛} 𝐽 = (\begin{matrix} 𝜆^{𝑛} & 𝑛 𝜆^{𝑛 - 1} \\ 0 & 𝜆^{𝑛} \end{matrix}) (\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix}) = (\begin{matrix} 𝜆^{𝑛 + 1} & 𝜆^{𝑛} + 𝑛 𝜆^{𝑛} \\ 0 & 𝜆^{𝑛 + 1} \end{matrix}) = (\begin{matrix} 𝜆^{𝑛 + 1} & (𝑛 + 1) 𝜆^{𝑛} \\ 0 & 𝜆^{𝑛 + 1} \end{matrix}),

which is the formula for $𝑛 + 1$ . By induction it holds for all $𝑛 \geq 1$ .

Over a field of characteristic $𝑝$ , the top right entry of $𝐽^{𝑝}$ is $𝑝 𝜆^{𝑝 - 1} = 0$ , so $𝐽^{𝑝} = 𝜆^{𝑝} 𝐼$ . For instance over $𝔽_{2}$ , ${(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})}^{2} = 𝐼$ .

Exercise A.2.8.standard Let $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴 𝐵 = 𝐵 𝐴$ .

(a)Show that $𝐴^{𝑘} 𝐵 = 𝐵 𝐴^{𝑘}$ for all $𝑘 \geq 0$ .
(b)Show that ${(𝐴 + 𝐵)}^{𝑚} =$ $\sum_{𝑘 = 0}^{𝑚} (\binom{𝑚}{𝑘}) 𝐴^{𝑘} 𝐵^{𝑚 - 𝑘}$ for all $𝑚 \geq 0$ .
(c)Show that (b) can fail for $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ .

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering), Definition 2.4.1 (Matrix product)

Hint 1. (a) is an induction on

𝑘

𝐴^{𝑘 + 1} 𝐵 =

𝐴 (𝐴^{𝑘} 𝐵)

Hint 2. For (b), multiply the formula for

𝑚

𝐴 + 𝐵

on the left, use (a) to write

𝐵 𝐴^{𝑘} 𝐵^{𝑚 - 𝑘} =

𝐴^{𝑘} 𝐵^{𝑚 - 𝑘 + 1}

, and combine terms with

(\binom{𝑚}{𝑘 - 1}) +

(\binom{𝑚}{𝑘}) =

(\binom{𝑚 + 1}{𝑘})

Hint 3. For (c), compute

{(𝐴 + 𝐵)}^{2}

and

𝐴^{2} + 2 𝐴 𝐵 + 𝐵^{2}

Sketch. (a)

𝐴^{𝑘 + 1} 𝐵 =

𝐴 𝐵 𝐴^{𝑘} =

𝐵 𝐴^{𝑘 + 1}

. (b)

{(𝐴 + 𝐵)}^{𝑚 + 1} =

\sum_{𝑘} (\binom{𝑚}{𝑘}) (𝐴^{𝑘 + 1} 𝐵^{𝑚 - 𝑘} + 𝐴^{𝑘} 𝐵^{𝑚 + 1 - 𝑘})

by (a), and Pascal’s rule collects the terms. (c)

{(𝐴 + 𝐵)}^{2} = 𝐼

but

𝐴^{2} +

2 𝐴 𝐵 +

𝐵^{2} =

2 𝐴 𝐵 =

(\begin{matrix} 2 & 0 \\ 0 & 0 \end{matrix})

(a) For $𝑘 = 0$ both sides are $𝐵$ . If $𝐴^{𝑘} 𝐵 = 𝐵 𝐴^{𝑘}$ , then $𝐴^{𝑘 + 1} 𝐵 =$ $𝐴 (𝐴^{𝑘} 𝐵) =$ $𝐴 (𝐵 𝐴^{𝑘}) =$ $(𝐴 𝐵) 𝐴^{𝑘} =$ $(𝐵 𝐴) 𝐴^{𝑘} =$ $𝐵 𝐴^{𝑘 + 1}$ .

(b) For $𝑚 = 0$ both sides are $𝐼$ . Suppose the formula holds for $𝑚$ . Then

{(𝐴 + 𝐵)}^{𝑚 + 1} = (𝐴 + 𝐵) \sum_{𝑘 = 0}^{𝑚} (\binom{𝑚}{𝑘}) 𝐴^{𝑘} 𝐵^{𝑚 - 𝑘} = \sum_{𝑘 = 0}^{𝑚} (\binom{𝑚}{𝑘}) 𝐴^{𝑘 + 1} 𝐵^{𝑚 - 𝑘} + \sum_{𝑘 = 0}^{𝑚} (\binom{𝑚}{𝑘}) 𝐵 𝐴^{𝑘} 𝐵^{𝑚 - 𝑘} .

By (a), $𝐵 𝐴^{𝑘} 𝐵^{𝑚 - 𝑘} =$ $𝐴^{𝑘} 𝐵^{𝑚 + 1 - 𝑘}$ . Shifting the index in the first sum ( $𝑘 + 1 \to 𝑘$ ),

{(𝐴 + 𝐵)}^{𝑚 + 1} = \sum_{𝑘 = 1}^{𝑚 + 1} (\binom{𝑚}{𝑘 - 1}) 𝐴^{𝑘} 𝐵^{𝑚 + 1 - 𝑘} + \sum_{𝑘 = 0}^{𝑚} (\binom{𝑚}{𝑘}) 𝐴^{𝑘} 𝐵^{𝑚 + 1 - 𝑘} = \sum_{𝑘 = 0}^{𝑚 + 1} (\binom{𝑚 + 1}{𝑘}) 𝐴^{𝑘} 𝐵^{𝑚 + 1 - 𝑘},

using $(\binom{𝑚}{𝑘 - 1}) +$ $(\binom{𝑚}{𝑘}) =$ $(\binom{𝑚 + 1}{𝑘})$ for $1 \leq 𝑘 \leq 𝑚$ and $(\binom{𝑚}{𝑚}) =$ $(\binom{𝑚 + 1}{𝑚 + 1}) =$ $(\binom{𝑚}{0}) =$ $(\binom{𝑚 + 1}{0}) =$ $1$ for the end terms.

(c) Here $𝐴 + 𝐵 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ , so ${(𝐴 + 𝐵)}^{2} = 𝐼$ . On the other hand $𝐴^{2} = 𝐵^{2} = 0$ and $𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , so $𝐴^{2} +$ $2 𝐴 𝐵 +$ $𝐵^{2} =$ $(\begin{matrix} 2 & 0 \\ 0 & 0 \end{matrix}) \neq$ $𝐼$ (also in characteristic $2$ , where it is $0$ ). The induction in (b) used $𝐴 𝐵 = 𝐵 𝐴$ in (a), and indeed $𝐵 𝐴 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) \neq 𝐴 𝐵$ .

Exercise A.2.9.standard Show that every integer

𝑛 \geq 1

can be written as a sum of distinct powers of

2

, and that this representation is unique up to the order of the terms.

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering)

Techniques. Uniqueness via two candidates (Technique 1.1.8), Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Let

2^{𝑘}

be the largest power of

2

with

2^{𝑘} \leq 𝑛

. Apply strong induction to

𝑛 - 2^{𝑘}

Hint 2. Why can

2^{𝑘}

not appear in the representation of

𝑛 - 2^{𝑘}

? Use

𝑛 < 2^{𝑘 + 1}

Hint 3. For uniqueness, show that

2^{𝑘}

must appear in every representation, because

1 +

2 +

\dots +

2^{𝑘 - 1} =

2^{𝑘} -

1 <

𝑛

Sketch. Strong induction. With

2^{𝑘} \leq 𝑛 < 2^{𝑘 + 1}

, the number

𝑚 = 𝑛 - 2^{𝑘} < 2^{𝑘}

0

or a sum of distinct powers of

2

, each less than

2^{𝑘}

, so adding

2^{𝑘}

gives

𝑛

. Every representation of

𝑛

uses

2^{𝑘}

(smaller powers sum to at most

2^{𝑘} - 1

) and no larger power, so removing

2^{𝑘}

leaves a representation of

𝑚

, which is unique by hypothesis.

We use strong induction on $𝑛 \geq 1$ . Let $𝑘 \geq 0$ be the largest integer with $2^{𝑘} \leq 𝑛$ (it exists because $2^{𝑗} > 𝑛$ for $𝑗 \geq 𝑛$ ), so that $2^{𝑘} \leq 𝑛 < 2^{𝑘 + 1}$ , and let $𝑚 = 𝑛 - 2^{𝑘}$ , so $0 \leq 𝑚 < 2^{𝑘}$ .

Existence. If $𝑚 = 0$ , then $𝑛 = 2^{𝑘}$ . Otherwise $1 \leq 𝑚 < 𝑛$ , so by the induction hypothesis $𝑚$ is a sum of distinct powers of $2$ , each at most $𝑚 < 2^{𝑘}$ . Adding the term $2^{𝑘}$ gives a representation of $𝑛$ with distinct terms.

Uniqueness. Take any representation of $𝑛$ as a sum of distinct powers of $2$ . No term exceeds $𝑛 < 2^{𝑘 + 1}$ , so all terms are among $1, 2, \dots, 2^{𝑘}$ . If $2^{𝑘}$ were not a term, the sum would be at most $1 +$ $2 +$ $\dots +$ $2^{𝑘 - 1} =$ $2^{𝑘} -$ $1 <$ $𝑛$ , by Example A.2.2 for $1 \times 1$ matrices over $ℚ$ with $𝐴 = 2$ . So $2^{𝑘}$ is a term, and the remaining terms form a representation of $𝑚$ (empty if $𝑚 = 0$ ). If $𝑚 \geq 1$ , this representation is unique by the induction hypothesis, since $𝑚 < 𝑛$ . So the representation of $𝑛$ is unique.

Exercise A.2.10.standard Let

𝑆 \subseteq ℤ

be a set with

𝑆 \neq {0}

and

𝑆 \neq \emptyset

that is closed under subtraction:

𝑎 - 𝑏 \in 𝑆

whenever

𝑎, 𝑏 \in 𝑆

. Show that

𝑆

has a least positive element

𝑑

, and that

𝑆 =

𝑑 ℤ =

{𝑑 𝑘 | 𝑘 \in ℤ}

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering), Proposition A.2.4 (Division with remainder)

Techniques. Double containment (Technique 1.3.14), Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. First show that

0 \in 𝑆

, that

𝑆

is closed under negation and addition, and that

𝑆

contains a positive element.

Hint 2. Take

𝑑

least positive in

𝑆

by well-ordering. Show

𝑑 ℤ \subseteq 𝑆

by induction on

| 𝑘 |

, or by closure under addition and negation.

Hint 3. For

𝑆 \subseteq 𝑑 ℤ

, divide

𝑎 \in 𝑆

𝑑

𝑎 = 𝑞 𝑑 + 𝑟

with

0 \leq 𝑟 < 𝑑

. Then

𝑟 = 𝑎 - 𝑞 𝑑 \in 𝑆

Sketch.

0 = 𝑎 - 𝑎

- 𝑏 = 0 - 𝑏

and

𝑎 + 𝑏 = 𝑎 - (- 𝑏)

lie in

𝑆

, and some nonzero

𝑎 \in 𝑆

gives a positive element

| 𝑎 |

. Let

𝑑

be the least positive element. Then

𝑑 ℤ \subseteq 𝑆

. For

𝑎 \in 𝑆

𝑎 = 𝑞 𝑑 + 𝑟

with

0 \leq 𝑟 < 𝑑

and

𝑟 = 𝑎 - 𝑞 𝑑 \in 𝑆

, so

𝑟 = 0

by minimality of

𝑑

Pick $𝑎 \in 𝑆$ . Then $0 = 𝑎 - 𝑎 \in 𝑆$ , so for every $𝑏 \in 𝑆$ also $- 𝑏 = 0 - 𝑏 \in 𝑆$ , and for $𝑎, 𝑏 \in 𝑆$ , $𝑎 + 𝑏 = 𝑎 - (- 𝑏) \in 𝑆$ . Since $𝑆 \neq {0}$ , it contains some $𝑎 \neq 0$ , and one of $𝑎$ and $- 𝑎$ is a positive element of $𝑆$ . By well-ordering (Theorem A.2.1(III)), $𝑆$ has a least positive element $𝑑$ .

By closure under addition, $𝑑, 2 𝑑, 3 𝑑, \dots \in 𝑆$ (induction on $𝑘$ : $(𝑘 + 1) 𝑑 = 𝑘 𝑑 + 𝑑$ ), and by closure under negation, so are $- 𝑑, - 2 𝑑, \dots$ ; also $0 \in 𝑆$ . So $𝑑 ℤ \subseteq 𝑆$ .

Conversely, let $𝑎 \in 𝑆$ . By Proposition A.2.4, $𝑎 = 𝑞 𝑑 + 𝑟$ with $0 \leq 𝑟 < 𝑑$ . Since $𝑞 𝑑 \in 𝑆$ , also $𝑟 = 𝑎 - 𝑞 𝑑 \in 𝑆$ . As $𝑑$ is the least positive element of $𝑆$ and $0 \leq 𝑟 < 𝑑$ , we get $𝑟 = 0$ , so $𝑎 = 𝑞 𝑑 \in 𝑑 ℤ$ .

A similar argument, with the degree in place of the absolute value, Theorem 7.1.14 in place of Proposition A.2.4, and the fact that $𝑝 (𝑇) = 0$ implies $(𝑞 𝑝) (𝑇) = 0$ for every polynomial $𝑞$ , shows that for an operator $𝑇$ on a finite-dimensional space, the polynomials $𝑝$ with $𝑝 (𝑇) = 0$ are exactly the multiples of one of least degree (Section 7.6).

Exercise A.2.11.hard Show that for every $𝑛 \geq 1$ ,

\frac{1 \cdot 3 \cdot 5 \dots (2 𝑛 - 1)}{2 \cdot 4 \cdot 6 \dots (2 𝑛)} \leq \frac{1}{\sqrt{3 𝑛}} .

(Induction on this inequality as stated does not work.)

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering)

Techniques. Strengthen the induction hypothesis (Technique A.2.5)

Hint 1. Let

𝑝_{𝑛}

be the left side, so

𝑝_{𝑛 + 1} =

𝑝_{𝑛} (2 𝑛 + 1) / (2 𝑛 + 2)

. Check that

𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛}

does not imply

𝑝_{𝑛 + 1} \leq 1 / \sqrt{3 𝑛 + 3}

: square and compare.

Hint 2. Prove instead the stronger bound

𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛 + 1}

Hint 3. The step reduces to

{(2 𝑛 + 1)}^{2} (3 𝑛 + 4) \leq

{(2 𝑛 + 2)}^{2} (3 𝑛 + 1)

. Expand both sides.

Sketch. Strengthen to

𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛 + 1}

. Base:

𝑝_{1} = 1 / 2

. Step:

𝑝_{𝑛 + 1} \leq

(2 𝑛 + 1) / ((2 𝑛 + 2) \sqrt{3 𝑛 + 1})

, and this is at most

1 / \sqrt{3 𝑛 + 4}

iff

{(2 𝑛 + 1)}^{2} (3 𝑛 + 4) \leq

{(2 𝑛 + 2)}^{2} (3 𝑛 + 1)

, which expands to

12 𝑛^{3} +

28 𝑛^{2} +

19 𝑛 +

4 \leq

12 𝑛^{3} +

28 𝑛^{2} +

20 𝑛 +

4

Let $𝑝_{𝑛}$ be the left side, so $𝑝_{1} = 1 / 2$ and $𝑝_{𝑛 + 1} =$ $𝑝_{𝑛} (2 𝑛 + 1) / (2 𝑛 + 2)$ .

The direct induction fails: from $𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛}$ we get $𝑝_{𝑛 + 1} \leq$ $(2 𝑛 + 1) / ((2 𝑛 + 2) \sqrt{3 𝑛})$ , and this is at most $1 / \sqrt{3 𝑛 + 3}$ only if ${(2 𝑛 + 1)}^{2} (3 𝑛 + 3) \leq$ ${(2 𝑛 + 2)}^{2} (3 𝑛)$ , that is, $12 𝑛^{3} +$ $24 𝑛^{2} +$ $15 𝑛 +$ $3 \leq$ $12 𝑛^{3} +$ $24 𝑛^{2} +$ $12 𝑛$ , which is false. (Technique A.2.5: the hypothesis leaves no room.)

We prove instead that $𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛 + 1}$ for all $𝑛 \geq 1$ , which implies the claim since $3 𝑛 + 1 > 3 𝑛$ . For $𝑛 = 1$ , $𝑝_{1} = 1 / 2 = 1 / \sqrt{4}$ . Suppose $𝑝_{𝑛} \leq 1 / \sqrt{3 𝑛 + 1}$ . Then

𝑝_{𝑛 + 1} \leq \frac{2 𝑛 + 1}{(2 𝑛 + 2) \sqrt{3 𝑛 + 1}},

and this is at most $1 / \sqrt{3 𝑛 + 4}$ if and only if ${(2 𝑛 + 1)}^{2} (3 𝑛 + 4) \leq$ ${(2 𝑛 + 2)}^{2} (3 𝑛 + 1)$ . Expanding,

{(2 𝑛 + 1)}^{2} (3 𝑛 + 4) = 12 𝑛^{3} + 28 𝑛^{2} + 19 𝑛 + 4, {(2 𝑛 + 2)}^{2} (3 𝑛 + 1) = 12 𝑛^{3} + 28 𝑛^{2} + 20 𝑛 + 4,

and $19 𝑛 \leq 20 𝑛$ . So $𝑝_{𝑛 + 1} \leq$ $1 / \sqrt{3 (𝑛 + 1) + 1}$ , completing the induction.

Exercise A.2.12.routine Find the error in the following argument.

Claim: $𝑛^{2} + 𝑛 + 1$ is even for every integer $𝑛 \geq 0$ . Proof: Suppose $𝑛^{2} + 𝑛 + 1$ is even. Then ${(𝑛 + 1)}^{2} +$ $(𝑛 + 1) +$ $1 =$ $(𝑛^{2} + 𝑛 + 1) +$ $2 (𝑛 + 1)$ is a sum of two even numbers, hence even. By induction, the claim holds for every $𝑛$ .

Solution.

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering)

Hint 1. Is the step correct? Is anything missing from the induction?

Hint 2. Try

𝑛 = 0

Sketch. The step is valid, but there is no base case, and it fails:

0^{2} + 0 + 1 = 1

is odd. In fact

𝑛^{2} + 𝑛 = 𝑛 (𝑛 + 1)

is always even, so

𝑛^{2} + 𝑛 + 1

is always odd.

The induction step is correct: it shows that

𝑃 (𝑛)

implies

𝑃 (𝑛 + 1)

. But (I) of Theorem A.2.1 also requires

𝑃 (0)

, which was never checked, and it is false:

0^{2} + 0 + 1 = 1

is odd. In fact the claim is false for every

𝑛

𝑛^{2} + 𝑛 = 𝑛 (𝑛 + 1)

is a product of consecutive integers, one of which is even, so

𝑛^{2} + 𝑛 + 1

is odd. The step proves “if

𝑃 (𝑛)

holds for some

𝑛

, then it holds for all larger

𝑛

”, which is vacuous here.

Exercise A.2.13.standard Find the error in the following argument.

Claim: Every operator on a nonzero finite-dimensional real vector space has an eigenvector. Proof: By induction on $𝑛 = dim 𝑉 \geq 1$ . If $𝑛 = 1$ , then $𝑉 = span (𝐯)$ for any $𝐯 \neq 𝟎$ , and $𝑇 (𝐯) = 𝜆 𝐯$ for some $𝜆 \in ℝ$ , so $𝐯$ is an eigenvector. Suppose the claim holds in dimension $𝑛$ , and let $dim 𝑉 = 𝑛 + 1$ and $𝑇 \in L (𝑉)$ . Pick a subspace $𝑊$ of $𝑉$ with $dim 𝑊 = 𝑛$ . By the induction hypothesis, the restriction of $𝑇$ to $𝑊$ has an eigenvector $𝐰 \in 𝑊$ , so $𝑇 (𝐰) = 𝜆 𝐰$ and $𝐰$ is an eigenvector of $𝑇$ .

Solution.

Uses. Definition 7.2.1 (Invariant subspace), Definition 7.2.6 (Eigenvalue, eigenvector)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. The induction hypothesis is about operators on

𝑛

-dimensional spaces. Is the restriction of

𝑇

𝑊

an operator on

𝑊

Hint 2. Test the argument on the rotation of

ℝ^{2}

by a right angle.

Sketch. The restriction of

𝑇

𝑊

is a map

𝑊 \to 𝑉

, and it is an operator on

𝑊

only if

𝑊

is invariant under

𝑇

. The rotation

𝑇 (𝑥, 𝑦) =

(- 𝑦, 𝑥)

ℝ^{2}

has no invariant line, and no eigenvector, so the claim itself is false.

The induction hypothesis applies to operators on $𝑛$ -dimensional spaces, that is, to linear maps $𝑊 \to 𝑊$ . The restriction of $𝑇$ to $𝑊$ is a linear map $𝑊 \to 𝑉$ , and it maps $𝑊$ into $𝑊$ only if $𝑊$ is invariant under $𝑇$ (Definition 7.2.1). The argument never chooses $𝑊$ invariant, and in general no invariant subspace of dimension $𝑛$ exists. Indeed the claim is false: the rotation $𝑇 (𝑥, 𝑦) =$ $(- 𝑦, 𝑥)$ of $ℝ^{2}$ has no eigenvector, since $𝑇 (𝑥, 𝑦) =$ $𝜆 (𝑥, 𝑦)$ gives $- 𝑦 = 𝜆 𝑥$ and $𝑥 = 𝜆 𝑦$ , so $𝑥 = - 𝜆^{2} 𝑥$ and $𝑦 = - 𝜆^{2} 𝑦$ , which forces $𝑥 = 𝑦 = 0$ because $- 𝜆^{2} \neq 1$ for real $𝜆$ .

This is the general warning of Section A.2.2. Inductions on dimension pass to a smaller space, and what is passed down must be an object of the kind the hypothesis is about. In Section 7.5 the induction works over $ℂ$ because an eigenvector exists, and the induction hypothesis is applied to an operator on a smaller space built from it.

More practice

The practice bank has 4 exercises on this section’s topics.