1.2 The Binomial Theorem

One polynomial does more work in this volume than any other: $(1 + x)^n$ . In analysis it bounds powers from below, and Section 1.4 makes $r^n$ large by keeping a single term of its expansion. In algebra it is the source of Fermat’s little theorem, which Chapter 4 proves by expanding $(x + y)^p$ in a field with $p$ elements. Both uses need the same theorem, so this section proves it once, in every commutative ring. The coefficients are defined by Pascal’s rule and never by division, which keeps the theorem valid in rings where $p!$ is $0$ . The school formula with factorials comes afterwards, as an identity between natural numbers that may then be read in $\mathbb{R}$ .

1.2.1. Binomial coefficients

Start with numbers you know. In school algebra, $(x + y)^2 = x^2 + 2xy + y^2$ , with coefficients $1, 2, 1$ . Multiply by $x + y$ : $(x + y)^3 = x^3 + (2 + 1) x^2 y + (1 + 2) x y^2 + y^3 = x^3 + 3x^2 y + 3xy^2 + y^3 .$ Each new coefficient is the sum of two neighboring coefficients of the row before.

In $(x + y)^n$ , each product $x^k y^{n-k}$ appears a certain number of times, and that number is the binomial coefficient. We define it by this rule of adding neighbors, Pascal’s rule, and we never divide.

Definition 1.2.1 (Binomial Coefficients)

The binomial coefficients $\binom{n}{k} \in \mathbb{N}$ , for $n, k \in \mathbb{N}$ , are defined by recursion on $n$ (Sets and Functions, Theorem 3.3.1, with $X$ the set of functions $\mathbb{N} \to \mathbb{N}$ ): $\begin{aligned} \binom{0}{0} &\mathrel{:=} 1 , & \binom{0}{k} &\mathrel{:=} 0 \quad (k \ge 1) , \\ \binom{n + 1}{0} &\mathrel{:=} 1 , & \binom{n + 1}{k + 1} &\mathrel{:=} \binom{n}{k} + \binom{n}{k + 1} \quad (k \in \mathbb{N}) . \end{aligned}$

In words: row $n + 1$ starts with $1$ , and each later entry is the sum of the two entries of row $n$ above it (Pascal’s rule). Each row is a whole function $\mathbb{N} \to \mathbb{N}$ , so the recursion has values for every $k$ , and a coefficient is a natural number, never a quotient.

Three facts follow by one induction on $n$ each.

$\binom{n}{k} = 0$ for $k > n$ . For $n = 0$ this is the definition. If it holds for $n$ and $k > n + 1$ , write $k = j + 1$ with $j > n$ ; then $\binom{n+1}{j+1} = \binom{n}{j} + \binom{n}{j+1} = 0 + 0$ .
$\binom{n}{n} = 1$ . Indeed $\binom{0}{0} = 1$ , and $\binom{n+1}{n+1} = \binom{n}{n} + \binom{n}{n+1} = 1 + 0$ by the first fact.
$\binom{n}{1} = n$ . Indeed $\binom{0}{1} = 0$ , and $\binom{n+1}{1} = \binom{n}{0} + \binom{n}{1} = 1 + n$ .

The rows $n = 0, \dots, 6$ , with the zeros for $k > n$ shown:

$n$	$k = 0$	$1$	$2$	$3$	$4$	$5$	$6$
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	2	1	0	0	0	0
3	1	3	3	1	0	0	0
4	1	4	6	4	1	0	0
5	1	5	10	10	5	1	0
6	1	6	15	20	15	6	1

The identity we need relates row $n + 1$ to row $n$ by a factor. It is what makes a prime divide the middle coefficients of row $p$ .

Proposition 1.2.1 (Absorption Identity)

For all $n, k \in \mathbb{N}$ , $(k + 1) \binom{n + 1}{k + 1} = (n + 1) \binom{n}{k} .$

Idea. The definition is a recursion on $n$ , so we induct on $n$ , proving the statement for all $k$ at once; the step then needs the hypothesis at two values of $k$ . In the step, expand the left side by Pascal’s rule, split the factor $k + 2$ as $(k + 1) + 1$ in front of one of the two terms, apply the hypothesis twice, and recombine with Pascal’s rule. For $n = 2$ , $k = 0$ it reads $1 \cdot 3 = 3 \cdot 1$ ; for $n = 3$ , $k = 1$ , $2 \cdot 6 = 4 \cdot 3$ .

Proof. We prove by induction on $n$ (Logic and Proof, Axiom 4.2.1) the statement “for every $k \in \mathbb{N}$ , $(k + 1)\binom{n+1}{k+1} = (n + 1)\binom{n}{k}$ ”.

Base $n = 0$ . For $k = 0$ : $1 \cdot \binom{1}{1} = 1 = 1 \cdot \binom{0}{0}$ . For $k \ge 1$ : $\binom{1}{k+1} = 0$ since $k + 1 > 1$ , and $\binom{0}{k} = 0$ ; both sides are $0$ .

Step. Suppose the statement holds for $n$ . For $k = 0$ , the claim for $n + 1$ reads $\binom{n+2}{1} = (n + 2)\binom{n+1}{0}$ , and both sides are $n + 2$ by the facts above. For $k = j + 1$ with $j \in \mathbb{N}$ , Pascal’s rule gives $\begin{aligned} (j + 2)\binom{n+2}{j+2} &= (j + 2)\binom{n+1}{j+1} + (j + 2)\binom{n+1}{j+2} \\ &= (j + 1)\binom{n+1}{j+1} + \binom{n+1}{j+1} + (j + 2)\binom{n+1}{j+2} \\ &= (n + 1)\binom{n}{j} + \binom{n+1}{j+1} + (n + 1)\binom{n}{j+1} \\ &= (n + 1)\binom{n+1}{j+1} + \binom{n+1}{j+1} = (n + 2)\binom{n+1}{j+1} , \end{aligned}$ where the third line uses the hypothesis at $k = j$ and at $k = j + 1$ , and the fourth line Pascal’s rule again. This is the claim for $n + 1$ at $k = j + 1$ . This proves the proposition.

1.2.2. Binomial coefficients and factorials

School defines $\binom{n}{k}$ as $\frac{n!}{k!\,(n-k)!}$ , with the factorial $n! = \prod_{k=1}^{n} k$ of Sets and Functions, Definition 3.3.1. The recursive definition and the school formula agree, and absorption is what shows it. We prove the agreement as an identity between natural numbers, with no division in it, and divide only at the end, in $\mathbb{R}$ .

Proposition 1.2.2 (Binomial Coefficients and Factorials)

Let $n, k \in \mathbb{N}$ with $k \le n$ .

(a) $\binom{n}{k} \, k! \, (n - k)! = n!$ .
(b) $\binom{n}{k} = \binom{n}{n-k}$ .
(c) $\binom{n}{k} \, k! = \prod_{j=0}^{k-1} (n - j)$ .

Hence, in $\mathbb{R}$ , $\binom{n}{k} = \dfrac{n!}{k!\,(n - k)!}$ .

In words: the table above is the table of the school formula, it is symmetric about the middle of each row, and $\binom{n}{k} \, k!$ is the product of the $k$ numbers $n, n - 1, \dots, n - k + 1$ .

Idea. Induct on $n$ , for all $k \le n$ at once, as in the absorption identity. In the step, write $(j + 1)! = j! \, (j + 1)$ ; absorption trades the factor $j + 1$ and the row $n + 1$ for a factor $n + 1$ and the row $n$ , and the hypothesis turns what is left into $n!$ . Parts (b) and (c) then compare two products equal to $n!$ and cancel a common factor, which is legal in $\mathbb{Z}$ because a product of non-zero integers is non-zero.

Proof. We prove (a) by induction on $n$ (Logic and Proof, Axiom 4.2.1), for every $k \le n$ at once. For $n = 0$ the only $k$ is $0$ , and $\binom{0}{0} \, 0! \, 0! = 1 = 0!$ .

Suppose (a) holds for $n$ , and let $k \le n + 1$ . If $k = 0$ , the left side is $1 \cdot 1 \cdot (n + 1)!$ . Otherwise $k = j + 1$ with $j \le n$ , and $(n + 1) - k = n - j$ . By the factorial recursion $(j + 1)! = j! \, (j + 1)$ , then Proposition 1.2.1, then the hypothesis at $j$ , $\begin{aligned} \binom{n+1}{j+1} \, (j + 1)! \, (n - j)! &= \Bigl[ (j + 1) \binom{n+1}{j+1} \Bigr] \, j! \, (n - j)! \\ &= (n + 1) \, \Bigl[ \binom{n}{j} \, j! \, (n - j)! \Bigr] = (n + 1) \, n! , \end{aligned}$ and $(n + 1) \, n! = (n + 1)!$ by the factorial recursion. This proves (a) for $n + 1$ . Parts (b) and (c) follow from (a) by cancelling a positive integer factor in $\mathbb{Z}$ .

For the formula in $\mathbb{R}$ , read each natural number $m$ as the real number $m \cdot 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Definition 4.2.1). By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.2.1 (a), the products in (a) are the same products in $\mathbb{R}$ , and by (b) there, $k! \, (n - k)! \ge 1 > 0$ . Dividing (a) by this positive real gives the formula. This proves the proposition.

Second readingProofs of (b) and (c): cancelling in the integers

Proof of (b). Let $c \mathrel{:=} k! \, (n - k)!$ , a positive integer, so $c \ne 0$ . By (a) at $k$ , $\binom{n}{k} c = n!$ . Since $n - k \le n$ and $n - (n - k) = k$ , (a) at $n - k$ gives $\binom{n}{n-k} (n - k)! \, k! = n!$ , that is, $\binom{n}{n-k} c = n!$ . Subtracting in $\mathbb{Z}$ , $\bigl( \binom{n}{k} - \binom{n}{n-k} \bigr) c = 0$ . A product of two integers is $0$ only if one factor is $0$ , and $c \ne 0$ . So $\binom{n}{k} - \binom{n}{n-k} = 0$ .

Proof of (c). First, $n! = (n - k)! \prod_{j=0}^{k-1} (n - j)$ for every $k \le n$ , by induction on $k$ . For $k = 0$ the product is empty, equal to $1$ , and both sides are $n!$ . If the claim holds for $k$ and $k + 1 \le n$ , then $n - k \ge 1$ , so the factorial recursion gives $(n - k)! = (n - k - 1)! \, (n - k)$ , and the product recursion appends the factor $j = k$ : $n! = (n - k - 1)! \, (n - k) \prod_{j=0}^{k-1} (n - j) = \bigl( n - (k + 1) \bigr)! \prod_{j=0}^{k} (n - j) .$ Now (a) and this claim give $\binom{n}{k} \, k! \, (n - k)! = (n - k)! \prod_{j=0}^{k-1} (n - j)$ . The factor $(n - k)!$ is a positive integer, so it cancels as $c$ did in (b). This proves (c).

Uses: Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 ( $\mathbb{Z}$ is an ordered ring); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (f) (no zero divisors).

The formula is a fact about natural numbers, and in $\mathbb{R}$ the division by $k! \, (n - k)!$ is legal because the divisor is a positive real. Chapter 4 works in a field with $p$ elements. There $p!$ is $0$ , and so is the divisor $k! \, (n - k)!$ as soon as $k \ge p$ or $n - k \ge p$ . For those $n$ and $k$ the formula cannot be written in that field, while the definition by Pascal’s rule makes sense for every $n$ and $k$ .

1.2.3. The binomial theorem

Expanding $(x + y)^n$ multiplies out $n$ factors $x + y$ and collects the products $x^k y^{n-k}$ . For $n = 2$ , in any ring, $(x + y)^2 = (x + y)x + (x + y)y = x^2 + yx + xy + y^2 .$ If $yx = xy$ , the two middle terms collect to $xy + xy = 2 \cdot (xy)$ , and the coefficients are $1, 2, 1$ , row $2$ of the table. In a commutative ring this collecting always works, and the counts are the binomial coefficients, acting as natural multiples.

Theorem 1.2.3 (The Binomial Theorem in a Commutative Ring)

Let $R$ be a commutative ring, $x, y \in R$ and $n \in \mathbb{N}$ . Then $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot \bigl( x^k y^{n-k} \bigr) .$

Here $\binom{n}{k} \cdot z$ is the natural multiple of Lemma 1.1.2 (in $\mathbb{R}$ , the product $\binom{n}{k} z$ ), and $n - k \in \mathbb{N}$ since $k \le n$ .

Idea. Induct on $n$ , with $(x + y)^{n+1} = (x + y)^n x + (x + y)^n y$ . Multiplying the sum for $(x + y)^n$ by $x$ raises every power of $x$ by one, which shifts the coefficients one place to the right; multiplying by $y$ leaves them in place. Adding the two rows entry by entry is exactly Pascal’s rule. The work is in lining the two sums up over the same range $k = 0, \dots, n + 1$ : the shifted sum gets a zero first term, and the other one a zero last term.

Before reading on: explain to yourself why the last term of the unshifted sum, at $k = n + 1$ , is $0$ .

Proof. Induction on $n$ (Logic and Proof, Axiom 4.2.1). For $n = 0$ , $(x + y)^0 = 1$ and the right side is $\binom{0}{0} \cdot (x^0 y^0) = 1 \cdot 1 = 1$ .

Suppose the formula holds for $n$ , and put $t_k \mathrel{:=} \binom{n}{k} \cdot (x^k y^{n-k})$ for $0 \le k \le n$ . The first equality below is the power recursion and the distributive law, (F9). The second is the induction hypothesis, with $x$ and $y$ multiplied into the sum term by term; this uses commutativity of multiplication, (F6). $(x + y)^{n+1} = (x + y)^n x + (x + y)^n y = \sum_{k=0}^{n} t_k x + \sum_{k=0}^{n} t_k y .$ The rule $(m \cdot a) b = m \cdot (ab)$ brings $x$ and $y$ inside the natural multiple (Lemma 1.1.2 (c)). Associativity of multiplication, (F5), commutativity and the power recursion then regroup the powers: $t_k x = \binom{n}{k} \cdot \bigl( x^{k+1} y^{n-k} \bigr) , \qquad t_k y = \binom{n}{k} \cdot \bigl( x^k y^{n+1-k} \bigr) .$ For $0 \le k \le n + 1$ let $z_k \mathrel{:=} x^k y^{n+1-k}$ , and define $u_0 \mathrel{:=} 0 , \quad u_k \mathrel{:=} \binom{n}{k - 1} \cdot z_k \ (1 \le k \le n + 1) , \qquad w_k \mathrel{:=} \binom{n}{k} \cdot z_k \ (0 \le k \le n + 1) .$ Then $t_k x = u_{k+1}$ and $t_k y = w_k$ for $0 \le k \le n$ , and $w_{n+1} = 0 \cdot z_{n+1} = 0$ , since $\binom{n}{n+1} = 0$ . Splitting off the first term $u_0 = 0$ of one sum and the last term $w_{n+1} = 0$ of the other gives $\sum_{k=0}^{n} t_k x = \sum_{k=0}^{n+1} u_k , \qquad \sum_{k=0}^{n} t_k y = \sum_{k=0}^{n+1} w_k .$ So $(x + y)^{n+1} = \sum_{k=0}^{n+1} (u_k + w_k)$ by Lemma 1.1.3 (a). Finally, $u_0 + w_0 = 0 + 1 \cdot z_0 = \binom{n+1}{0} \cdot z_0$ . For $k = j + 1$ with $0 \le j \le n$ , the sum rule $m \cdot z + m' \cdot z = (m + m') \cdot z$ and Pascal’s rule give $u_k + w_k = \binom{n}{j} \cdot z_k + \binom{n}{j + 1} \cdot z_k = \binom{n + 1}{j + 1} \cdot z_k = \binom{n + 1}{k} \cdot z_k .$ Hence $(x + y)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} \cdot (x^k y^{n+1-k})$ , which is the formula for $n + 1$ . This proves the theorem.

Uses: Lemma 1.1.3 (b) (constant times a sum), (f) (split off first term); Sets and Functions, Definition 3.3.1 (last term split off); Lemma 1.1.2 (a) (sum rule); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (h) (same rule, no order needed).

The proof used commutativity, (F6), at every regrouping of $x^k y^{n-k} x$ , and the theorem needs it. The linear-algebra volumes meet matrices, whose multiplication is not commutative. For matrices the expansion can fail for pairs that do not commute, already at $n = 2$ . For $R = \mathbb{Z}$ the theorem is the familiar expansion, since there $m \cdot z = mz$ (Lemma 1.1.2 (e)). The same holds in $\mathbb{R}$ , where $m \cdot 1$ is the real number $m$ . From here on we read the theorem in $\mathbb{R}$ this way.

Second readingWhat goes wrong without commutativity

Keep every clause of a commutative ring except commutativity of multiplication, (F6), together with the distributive law on the other side, $(a + b)c = ac + bc$ , which (F6) used to supply. Then the theorem fails already at $n = 2$ . Expanding by the two distributive laws gives $(x + y)^2 = x^2 + xy + yx + y^2$ , and the theorem’s middle term $2 \cdot (xy) = xy + xy$ agrees with $xy + yx$ exactly when $yx = xy$ . The $2 \times 2$ real matrices $X = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} , \qquad Y = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ live in a system with all of these laws under the usual matrix operations. Here $X^2 = Y^2 = 0$ , while $(X + Y)^2$ is the identity matrix and $2 \cdot (XY)$ has entries $2, 0, 0, 0$ . Everything else in the proof survives: Pascal’s rule, the sum rules and the bookkeeping with $u_k$ and $w_k$ . Only the regrouping $x^k y^{n-k} x = x^{k+1} y^{n-k}$ breaks, and this is why the statement asks for a commutative ring.

Example (Three expansions)

(a) Expand $(a + b)^4$ in $\mathbb{Z}$ . (b) Expand $(x - 1)^5$ in $\mathbb{R}$ . (c) Compute $11^4$ from row $4$ of the table.

Solution.

(a) The theorem with $n = 4$ and row $4$ , $1, 4, 6, 4, 1$ , gives, from $k = 4$ down to $k = 0$ , $(a + b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4ab^3 + b^4 .$
(b) Take $y = -1$ in the theorem. The term with index $k$ is $\binom{5}{k} x^k (-1)^{5-k}$ , and $(-1)^{5-k}$ is $-1$ for $k = 4, 2, 0$ and $1$ for $k = 5, 3, 1$ , since $(-1)^2 = 1$ and Sets and Functions, Proposition 3.3.4 (a), (b) give $(-1)^{2i} = 1$ and $(-1)^{2i+1} = -1$ . With row $5$ , $1, 5, 10, 10, 5, 1$ , $(x - 1)^5 = x^5 - 5x^4 + 10x^3 - 10x^2 + 5x - 1 .$
(c) Write $11 = 10 + 1$ and take $x = 10$ , $y = 1$ : $11^4 = 10^4 + 4 \cdot 10^3 + 6 \cdot 10^2 + 4 \cdot 10 + 1 = 10000 + 4000 + 600 + 40 + 1 = 14641 .$ The digits of $14641$ are row $4$ , because every coefficient of that row is below $10$ and no carrying occurs.

Quick check. Write row $7$ from row $6$ by Pascal’s rule, and check $\binom{7}{3}$ by the formula of Proposition 1.2.2.

Solution. Row $6$ is $1, 6, 15, 20, 15, 6, 1$ , so row $7$ is $1, 7, 21, 35, 35, 21, 7, 1$ (for instance $\binom{7}{3} = \binom{6}{2} + \binom{6}{3} = 15 + 20$ ). By the formula, $\binom{7}{3} = \frac{7!}{3! \, 4!} = \frac{5040}{6 \cdot 24} = \frac{5040}{144} = 35$ .

Warning. The rule $(x + y)^n = x^n + y^n$ is false in $\mathbb{R}$ for every $n \ge 2$ : with $x = y = 1$ it would give $2^n = 2$ , while $2^n > 2^1 = 2$ for $n \ge 2$ (Sets and Functions, Proposition 3.3.4 (e)); at $n = 2$ , $(1 + 1)^2 = 4 \ne 2$ . The theorem says what is missing: the middle terms $\binom{n}{k} x^k y^{n-k}$ with $0 < k < n$ . Chapter 4 shows that those middle terms all vanish for $n = p$ in every field of characteristic $p$ , a prime.

1.2.4. Consequences in the real numbers

In $\mathbb{R}$ the theorem gives exact sums of binomial coefficients. For $x \ge 0$ it also gives lower bounds for $(1 + x)^n$ : every term of the expansion is then non-negative, and a sum of non-negative terms is at least any part of it. These lower bounds are what Section 1.4 needs.

Corollary 1.2.4 (Binomial Sums and Lower Bounds)

Let $n \in \mathbb{N}$ .

(a) $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ , and $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ if $n \ge 1$ .
(b) If $x \in \mathbb{R}$ , $x \ge 0$ and $k \le n$ , then $(1 + x)^n \ge \binom{n}{k} x^k$ .
(c) If $x \in \mathbb{R}$ , $x \ge 0$ and $n \ge 2$ , then $(1 + x)^n \ge 1 + nx + \frac{n(n-1)}{2} x^2$ .

Proof. We apply Theorem 1.2.3 in $R = \mathbb{R}$ .

(a) With $x = y = 1$ , every $x^k y^{n-k}$ is $1$ , since $1^m = 1$ for every $m$ , so $2^n = (1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k}$ . With $x = -1$ and $y = 1$ , $(-1 + 1)^n = 0^n$ , and for $n \ge 1$ , $0^n = 0^{n-1} 0 = 0$ . So $0 = \sum_{k=0}^{n} (-1)^k \binom{n}{k}$ .

(b), (c) With $y = 1$ , $(x + 1)^n = \sum_{j=0}^{n} \binom{n}{j} x^j$ . For $x \ge 0$ each term is $\ge 0$ . Indeed $\binom{n}{j} \ge 0$ is a natural number. Also $x^j \ge 0$ : for $x > 0$ a power of a positive number is positive, and for $x = 0$ , $x^j$ is $1$ or $0$ . A product of two non-negative numbers is non-negative. By Proposition 1.1.5 (b), the sum is at least its single term $j = k$ , which is (b). By the same part with $m = 2 \le n$ , it is at least the sum of its terms $j = 0, 1, 2$ , which is $1 + \binom{n}{1} x + \binom{n}{2} x^2$ . Finally, $\binom{n}{1} = n$ by the third fact after Definition 1.2.1. By Proposition 1.2.2 (c) with $k = 2$ , $\binom{n}{2} \cdot 2 = n(n - 1)$ , so $\binom{n}{2} = \frac{n(n-1)}{2}$ . This proves (c).

Uses: Sets and Functions, Proposition 3.3.4 (e) (positive powers of positives); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d) (multiplying non-negative inequalities); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.2.1 (a), (b) (naturals in $\mathbb{R}$ : products, sign).

For $n \ge 1$ , keeping only the first two terms gives $(1 + x)^n \ge 1 + nx$ for $x \ge 0$ , by Proposition 1.1.5 (b) with $m = 1$ . Sets and Functions proved this as Bernoulli’s inequality (Sets and Functions, Theorem 3.3.7), and here we recover it on that range. Bernoulli’s inequality also covers $-1 \le x < 0$ , and the expansion cannot reach that range: for $x < 0$ the terms $\binom{n}{j} x^j$ alternate in sign, and dropping some of them may raise the sum instead of lowering it.

Quick check. With $n = 5$ and $x = 2$ , which $k$ gives the best lower bound for $3^5$ from (b)?

Solution. The bound is $\binom{5}{k} 2^k$ , which for $k = 0, 1, \dots, 5$ is $1, 10, 40, 80, 80, 32$ . The best choices are $k = 3$ and $k = 4$ , both giving $3^5 = 243 \ge 80$ . A single term loses a lot; Section 1.4 only ever needs a bound that grows fast enough, not a sharp one.

Example (A lower bound for powers of two)

Show that $2^n \ge \frac{n(n-1)}{2}$ , and hence $\frac{n}{2^n} \le \frac{2}{n - 1}$ , for every integer $n \ge 2$ .

Solution. Let $n \ge 2$ . By Corollary 1.2.4 (b) with $x = 1$ and $k = 2 \le n$ , $2^n = (1 + 1)^n \ge \binom{n}{2} = \frac{n(n-1)}{2}$ . Both sides are positive ( $n(n - 1) \ge 2$ ), so Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (c) inverts the inequality: $\frac{1}{2^n} \le \frac{2}{n(n-1)}$ . Multiplying by $n > 0$ gives $\frac{n}{2^n} \le \frac{2}{n - 1}$ . For instance, at $n = 5$ : $\frac{5}{32} \le \frac{2}{4}$ .

The right side $\frac{2}{n - 1}$ can be made as small as we like by taking $n$ large, and Section 1.4 turns this into the limit $n/2^n \to 0$ .

Example (An absorbed sum)

Compute $\sum_{k=1}^{4} k \binom{4}{k}$ in two ways: term by term, and by absorption.

Solution. Term by term, with row $4$ : $1 \cdot 4 + 2 \cdot 6 + 3 \cdot 4 + 4 \cdot 1 = 4 + 12 + 12 + 4 = 32$ .

By absorption: shift the index by $k = j + 1$ (Sets and Functions, Definition 3.3.1), so the sum is $\sum_{j=0}^{3} (j + 1) \binom{4}{j+1}$ . Proposition 1.2.1 with $n = 3$ gives $(j + 1) \binom{4}{j+1} = 4 \binom{3}{j}$ . The constant $4$ comes out of the sum by Lemma 1.1.3 (b). The row sum Corollary 1.2.4 (a) for $n = 3$ then gives $\sum_{k=1}^{4} k \binom{4}{k} = \sum_{j=0}^{3} 4 \binom{3}{j} = 4 \sum_{j=0}^{3} \binom{3}{j} = 4 \cdot 2^3 = 32 .$

The second computation never uses the entries of row $4$ : absorption turns the factor $k$ into the constant $4$ , and what is left is all of row $3$ , whose sum is $2^3$ .

1.2.5. Exercises

A. Check your understanding

Exercise (A1)

(a) In the proof of Theorem 1.2.3, why is $u_0 \mathrel{:=} 0$ put in, and where is it used?
(b) Where does the proof use commutativity of multiplication, (F6)?
(c) Run the induction step from $n = 1$ to $n = 2$ : list $u_0, u_1, u_2$ and $w_0, w_1, w_2$ , and add them.
(d) True or false: $\binom{n}{k} = \binom{n}{n-k}$ for all $n, k \in \mathbb{N}$ with $k \le n$ . Give the reason.

Solution.

(a) The sum $\sum_{k=0}^{n} t_k x$ is $u_1 + \dots + u_{n+1}$ , which starts at index $1$ . Putting in $u_0 = 0$ turns it into $\sum_{k=0}^{n+1} u_k$ by Lemma 1.1.3 (f) (split off the first term, which is $0$ ). That is a sum over the same range $0 \le k \le n + 1$ as $\sum w_k$ , so the two can be added termwise by Lemma 1.1.3 (a).
(b) In computing $t_k x$ : the product $(x^k y^{n-k}) x$ becomes $x^{k+1} y^{n-k}$ only after $x$ is moved past $y^{n-k}$ , which is commutativity, (F6). It is also used to bring the factor $x$ (and $y$ ) to the left of the sum, where Lemma 1.1.3 (b) has it. The first use is the one the theorem cannot do without: for matrices that do not commute, $(x + y)^2 = x^2 + xy + yx + y^2$ , and $xy + yx \ne 2 \cdot xy$ .
(c) For $n = 1$ , $z_k = x^k y^{2-k}$ . Then $u_0 = 0$ , $u_1 = \binom{1}{0} \cdot z_1 = xy$ , $u_2 = \binom{1}{1} \cdot z_2 = x^2$ ; and $w_0 = \binom{1}{0} \cdot z_0 = y^2$ , $w_1 = \binom{1}{1} \cdot z_1 = xy$ , $w_2 = \binom{1}{2} \cdot z_2 = 0$ . The sum is $y^2 + 2 \cdot (xy) + x^2$ , with coefficients $1, 2, 1$ , row $2$ .
(d) True, by Proposition 1.2.2 (b). Each row of the table reads the same from both ends.

B. Practice

Exercise (B1: Expansions)

(a) Write $(2x - 1)^5$ , for $x \in \mathbb{R}$ , as a sum of six terms. What multiplies $x^3$ ? (b) Compute $\sum_{k=0}^{n} \binom{n}{k} 3^k$ for $n \in \mathbb{N}$ .

Solution.

(a) Since $(2x)^k = 2^k x^k$ (Sets and Functions, Proposition 3.3.4 (c)), the theorem with $2x$ in place of $x$ and $y = -1$ gives $(2x - 1)^5 = \sum_{k=0}^{5} \binom{5}{k} 2^k (-1)^{5-k} x^k .$ Term by term, with row $5$ and $k = 5, 4, \dots, 0$ , this is $(2x - 1)^5 = 32x^5 - 80x^4 + 80x^3 - 40x^2 + 10x - 1$ . The term with $k = 3$ is $\binom{5}{3} \cdot 8 \cdot (-1)^2 \, x^3 = 80 x^3$ , so $80$ multiplies $x^3$ .
(b) By the theorem with $x = 3$ and $y = 1$ , the sum is $(3 + 1)^n = 4^n$ . Check $n = 2$ : $1 + 2 \cdot 3 + 9 = 16$ .

Exercise (B2: An absorbed sum)

Show that $\sum_{k=1}^{n} k \binom{n}{k} = n \, 2^{n-1}$ for every integer $n \ge 1$ .

Hint: absorption.

Solution. Let $n \ge 1$ . Shift the index by $k = j + 1$ (Sets and Functions, Definition 3.3.1): the sum is $\sum_{j=0}^{n-1} (j + 1) \binom{n}{j+1}$ . By Proposition 1.2.1 with $n - 1 \in \mathbb{N}$ in place of $n$ , $(j + 1) \binom{(n-1)+1}{j+1} = n \binom{n-1}{j}$ . Taking the constant $n$ out of the sum and using the row sum Corollary 1.2.4 (a) for $n - 1$ , $\sum_{k=1}^{n} k \binom{n}{k} = \sum_{j=0}^{n-1} n \binom{n-1}{j} = n \sum_{j=0}^{n-1} \binom{n-1}{j} = n \, 2^{n-1} .$ Check $n = 3$ : $1 \cdot 3 + 2 \cdot 3 + 3 \cdot 1 = 12 = 3 \cdot 4$ .

Uses: Lemma 1.1.3 (b) (constant out of a sum).

Exercise (B3: A numerical lower bound)

Show that $(1.01)^{10} \ge 1.1045$ without multiplying out the power.

Solution. Apply Corollary 1.2.4 (c) with $x = 0.01 \ge 0$ and $n = 10 \ge 2$ : $\frac{n(n-1)}{2} = 45$ , and $(1.01)^{10} \ge 1 + 10 \cdot 0.01 + 45 \cdot 0.0001 = 1 + 0.1 + 0.0045 = 1.1045 .$

C. Going deeper

Exercise (C1: Chapter check: absorption twice)

Prove that, in $\mathbb{Z}$ , $\sum_{k=0}^{n} k(k - 1) \binom{n}{k} = n(n - 1) \, 2^{n-2}$ for every integer $n \ge 2$ .

Solution. Let $n \ge 2$ , and write $a_k \mathrel{:=} k(k - 1) \binom{n}{k}$ . The terms $a_0$ and $a_1$ are $0$ , so by Proposition 1.1.4 (b) with $m = 1$ , $\sum_{k=0}^{n} a_k = (a_0 + a_1) + \sum_{k=2}^{n} a_k = \sum_{k=2}^{n} a_k .$ Let $2 \le k \le n$ . By Proposition 1.2.1 with $n - 1$ in place of $n$ and $k - 1$ in place of $k$ (both in $\mathbb{N}$ , as $n, k \ge 1$ ), $k \binom{n}{k} = n \binom{n-1}{k-1}$ . Applied again with $n - 2$ and $k - 2$ (in $\mathbb{N}$ , as $n, k \ge 2$ ), $(k - 1) \binom{n-1}{k-1} = (n - 1) \binom{n-2}{k-2}$ . Hence $a_k = (k - 1) \cdot k \binom{n}{k} = n \, (k - 1) \binom{n-1}{k-1} = n(n - 1) \binom{n-2}{k-2} .$ Shifting the index by $j = k - 2$ , taking the constant $n(n - 1)$ out of the sum and using the row sum Corollary 1.2.4 (a) for $n - 2$ , $\sum_{k=2}^{n} a_k = n(n - 1) \sum_{j=0}^{n-2} \binom{n-2}{j} = n(n - 1) \, 2^{n-2} .$ Check $n = 3$ : $a_2 + a_3 = 2 \cdot 3 + 6 \cdot 1 = 12 = 6 \cdot 2$ .

Uses: Sets and Functions, Definition 3.3.1 (index shift); Lemma 1.1.3 (b) (constant out of a sum).

What a complete answer needs. (10 points) - 2: the terms $k = 0, 1$ are shown to be $0$ and split off, with the splitting rule cited. - 3: the first absorption, $k \binom{n}{k} = n \binom{n-1}{k-1}$ , with its range $k \ge 1$ stated. - 3: the second absorption, $(k - 1) \binom{n-1}{k-1} = (n - 1) \binom{n-2}{k-2}$ , with its range $k \ge 2$ , $n \ge 2$ stated. - 2: the index shift and the row sum Corollary 1.2.4 (a) for $n - 2$ . A route through Proposition 1.2.2 (c) earns the absorption points for the equivalent identity $k(k - 1) \binom{n}{k} = n(n - 1) \binom{n-2}{k-2}$ , proved for $k \ge 2$ . An induction on $n$ from $n = 2$ , with Pascal’s rule and Exercise (B2: An absorbed sum), also earns full marks. It scores 3 for the base case and the set-up, 4 for the Pascal split $S(n + 1) = 2S(n) + 2 \sum_{j=0}^{n} j \binom{n}{j}$ , where $S(n)$ is the sum, and 3 for the algebra with B2.

Slips that lose the step. Applying absorption at $k = 0$ , where it would need $\binom{n-1}{-1}$ , earns 0 for that step.

$n$	$k = 0$	$1$	$2$	$3$	$4$	$5$	$6$
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	2	1	0	0	0	0
3	1	3	3	1	0	0	0
4	1	4	6	4	1	0	0
5	1	5	10	10	5	1	0
6	1	6	15	20	15	6	1

$n$	$k = 0$	$1$	$2$	$3$	$4$	$5$	$6$
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	2	1	0	0	0	0
3	1	3	3	1	0	0	0
4	1	4	6	4	1	0	0
5	1	5	10	10	5	1	0
6	1	6	15	20	15	6	1

$n$	$k = 0$	$1$	$2$	$3$	$4$	$5$	$6$
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	2	1	0	0	0	0
3	1	3	3	1	0	0	0
4	1	4	6	4	1	0	0
5	1	5	10	10	5	1	0
6	1	6	15	20	15	6	1