Mathematics 243 – Algebraic Structures Selected Solutions – Problem Set 5 October 16, 2006

2.2/21. To show: \binom{n}{r} + \binom{n}{r−1} = \binom{n+1}{r} for all 1 ≤ r ≤ n. For this we do not need a proof by induction. We can simply use the definition of the binomial coefficients in terms of quotients of factorials, and simplify by putting terms over a common denominator:

\binom{n}{r} + \binom{n}{r − 1} = \frac{n!}{r!(n − r)!} + \frac{n!}{(r − 1)!(n − r + 1)!}

= \frac{n!(n − r + 1)}{r!(n − r + 1)!} + \frac{n!r}{r!(n − r + 1)!}

= \frac{n!(n − r + 1 + r)}{r!(n − r + 1)!}

= \frac{n!(n + 1)}{r!(n − r + 1)!}

= \frac{(n + 1)!}{r!(n + 1 − r)!}

= \binom{n + 1}{r}

2.2/23. We want to prove the binomial theorem:

(a + b)^{n} = ∑_{ℓ=0}^{n} \binom{n}{ℓ}a^{n−ℓ}b^{ℓ}

for all n ≥ 1. (The formulas actually work with n = 0 also.)

We will take the base case as n = 1. Then \binom{1}{0} = \frac{1!}{0!1!} = 1 and \binom{1}{1} = \frac{1!}{1!0!} = 1. Hence

(a + b)^{1} = a + b = \binom{1}{0}a + \binom{1}{1}b

is true.

Now assume that the theorem is true for n = k:

(a + b)^{k} = ∑_{ℓ=0}^{k} \binom{k}{ℓ}a^{k−ℓ}b^{ℓ}

and consider the case n = k + 1. We will start from (a + b)^{k+1} and apply the induction hypothesis:

(a + b)^{k+1} = (a + b)^{k}(a + b)

= (∑_{ℓ=0}^{k} \binom{k}{ℓ}a^{k−ℓ}b^{ℓ}) (a + b)

= (\binom{k}{0}a^{k} + ∑_{ℓ=1}^{k−1} \binom{k}{ℓ}a^{k−ℓ}b^{ℓ} + \binom{k}{k}b^{k}) (a + b)

Expand out the product completely using the distributive law, and collect like terms. The “end terms” are \binom{k}{0}a^{k} · a = a^{k+1} = \binom{k+1}{0}a^{k+1} and \binom{k}{k}b^{k} · b = b^{k+1} = \binom{k+1}{k+1}b^{k+1} (since \binom{k+1}{0} = \binom{k+1}{k+1} = 1). In all other cases, for each given ℓ, 1 ≤ ℓ ≤ k, there are two different products that yield the same a^{k+1−ℓ}b^{ℓ}, namely:

\binom{k}{ℓ − 1}a^{k−(ℓ−1)}b^{ℓ−1} · b + \binom{k}{ℓ}a^{k−ℓ}b^{ℓ} · a = (\binom{k}{ℓ − 1} + \binom{k}{ℓ}) a^{k+1−ℓ}b^{ℓ}

By the result of problem 21, the sum of binomial coefficents in the parentheses here is \binom{k+1}{ℓ} so the product

(∑_{ℓ=0}^{k} \binom{k}{ℓ}a^{k−ℓ}b^{ℓ}) (a + b) = ∑_{ℓ=0}^{k+1} \binom{k + 1}{ℓ}a^{k+1−ℓ}b^{ℓ},

which is what we wanted to show.

2.3/20. We want to show that if a, b are integers such that a|b and b|a, then a = b or a = −b. The hypothesis implies that there are integers p, q such that

(1)  a = bp and b = aq.

If either a = 0 or b = 0 then both a, b = 0, and the conclusion follows since 0 = ±0. Hence we may assume a, b ≠ 0 in the remainder of the proof. If we substitute from the first equation in (1) above into the second, then we get the equation b = (bp)q = b(pq). Since we are assuming b ≠ 0, this implies pq = 1. But the only two ways two integers p, q can multiply to give 1 are p = q = 1 or p = q = −1. In the first case, a = b. In the second, a = −b. This is what we wanted to show.