Applications: divisibility, estimates, identities

The binomial theorem is more than a formula for expanding $(a + b)^n$. It is a tool that produces clean proofs of divisibility statements, quick numerical estimates that would be impossibly tedious by hand, and combinatorial identities that resist direct attack. This subtopic showcases the three most common application patterns.

1. Divisibility proofs

The pattern: to show $A^n$ is divisible by some integer $d$, write $A = d \cdot k + r$ (or some other splitting), expand using the binomial theorem, and identify the divisibility.

Template. To prove $a^n - 1$ is divisible by $a - 1$: write $a = 1 + (a - 1)$ and expand. Or simpler: $a^n - 1 = (a - 1)(a^{n-1} + a^{n-2} + \dots + 1)$.

To prove $a^n - b^n$ divisible by $a - b$, expand $a = b + (a - b)$: $a^n = (b + (a - b))^n = b^n + n b^{n-1}(a - b) + \binom{n}{2} b^{n-2} (a - b)^2 + \dots$ Subtract $b^n$: every remaining term has $(a - b)$ as a factor.

Worked Example A. Show $9^n - 8n - 1$ is divisible by $64$ for all $n \in \mathbb{N}$.

Write $9 = 1 + 8$. Then $9^n = (1 + 8)^n = \sum_{r=0}^n \binom{n}{r} 8^r = 1 + 8n + \binom{n}{2} 64 + \binom{n}{3} 512 + \dots$ So $9^n - 8n - 1 = \binom{n}{2} 64 + \binom{n}{3} 512 + \dots = 64 \left[\binom{n}{2} + 8 \binom{n}{3} + \dots\right]$, divisible by $64$.

Worked Example B. Show $4^n + 15n - 1$ is divisible by $9$.

$4 = 1 + 3$. $4^n = (1 + 3)^n = 1 + 3n + \binom{n}{2} 9 + \binom{n}{3} 27 + \dots$ So $4^n + 15n - 1 = 18n + \binom{n}{2} 9 + \dots = 9(2n + \binom{n}{2} + \dots)$, divisible by $9$.

2. Numerical estimates

When $n$ is moderate and the binomial $(a + b)^n$ has $b$ small compared to $a$, the early terms of the expansion dominate. We can compute approximations to high accuracy.

Worked Example C. Compute $(1.01)^{10}$ to four decimals.

$(1.01)^{10} = (1 + 0.01)^{10} = \sum_{r=0}^{10} \binom{10}{r}(0.01)^r$.

• $r = 0$: $1$.
• $r = 1$: $10 \cdot 0.01 = 0.1$.
• $r = 2$: $45 \cdot 0.0001 = 0.0045$.
• $r = 3$: $120 \cdot 0.000001 = 0.00012$.
• $r = 4$: $210 \cdot 10^{-8} \approx 0.0000021$.

Sum: $1.1046221 \approx 1.1046$. (Exact value $1.10462...$)

Worked Example D. Find $(99)^4$ using $99 = 100 - 1$.

$(100 - 1)^4 = 100^4 - 4 \cdot 100^3 + 6 \cdot 100^2 - 4 \cdot 100 + 1 = 100\,000\,000 - 4\,000\,000 + 60\,000 - 400 + 1 = 96\,059\,601$.

3. Identity proofs

Many identities involving binomial coefficients fall out of expanding $(1 + x)^n$ and either substituting a clever value of $x$, or comparing coefficients.

Worked Example E. Prove $\sum_{r=0}^n r(r-1)\binom{n}{r} = n(n-1) 2^{n-2}$ for $n \ge 2$.

Differentiate $(1 + x)^n = \sum \binom{n}{r} x^r$ twice with respect to $x$: $n(n-1)(1 + x)^{n-2} = \sum_{r=0}^n r(r - 1)\binom{n}{r} x^{r-2}.$ Set $x = 1$: $n(n - 1) 2^{n-2} = \sum_{r=0}^n r(r - 1)\binom{n}{r}. \qed$

This differentiation trick is enormously powerful , it converts a sum involving $r$, $r^2$, etc. into a sum we already know.

Worked examples (mixed)

Example 1. Show $5^n - 1$ is divisible by $4$ for all $n \in \mathbb{N}$.

$5 = 1 + 4$. $5^n = 1 + 4n + \binom{n}{2} 16 + \dots$ So $5^n - 1 = 4n + \binom{n}{2} 16 + \dots = 4(n + 4\binom{n}{2} + \dots)$, divisible by $4$.

Example 2. Find the last two digits of $7^{1000}$. (Hint: work mod $100$.)

$7^4 = 2401 \equiv 1 \pmod{100}$. So $7^{1000} = (7^4)^{250} \equiv 1 \pmod{100}$. Last two digits: $01$.

Example 3. Compute $\sum_{r=0}^{10} \binom{10}{r} 2^r$.

This is $(1 + 2)^{10} = 3^{10} = 59049$.

Example 4. Show $(1.001)^{1000} > 2$.

By the binomial theorem, $(1 + 0.001)^{1000} = 1 + 1000 \cdot 0.001 + \binom{1000}{2} (0.001)^2 + \dots > 1 + 1 = 2$.

Example 5. Find the integral part of $(\sqrt{3} + 1)^6$.

$(\sqrt{3} + 1)^6 + (\sqrt{3} - 1)^6 = 2[\binom{6}{0} 3^3 + \binom{6}{2} 3^2 + \binom{6}{4} 3 + \binom{6}{6}] = 2[27 + 135 + 45 + 1] = 416$. Since $0 < (\sqrt{3} - 1)^6 < 1$, we get $(\sqrt{3} + 1)^6 = 416 - (\sqrt{3} - 1)^6$, so the integral part is $415$.

Try it yourself

1. Show $3^{2n} - 1$ is divisible by $8$ for all $n \in \mathbb{N}$.
2. Show $6^n - 5n + 4$ is divisible by $25$ for all $n \ge 2$. (Adjust as needed.)
3. Compute $(1.02)^7$ to four decimals.
4. Find $(101)^5$ exactly using $101 = 100 + 1$.
5. Show $7^{2n} - 1$ is divisible by $48$.
6. Find the last digit of $7^{2026}$.
7. Compute $\sum_{r=0}^{n} 2^r \binom{n}{r}$.
8. Show $(\sqrt{2} + 1)^{10} + (\sqrt{2} - 1)^{10}$ is rational.
9. Prove $(2)^{n+1} > 2n + 1$ for $n \ge 2$. (Hint: binomial expansion of $2^{n+1} = (1+1)^{n+1}$.)
10. Show $10^n - 1$ is divisible by $9$.
11. Estimate $(0.99)^{100}$ correct to three decimals.
12. Prove $\sum_{r=0}^{n} \binom{n}{r} 3^r = 4^n$.

Pitfalls / Tricks

• When proving divisibility, expand using the form $a = (\text{multiple of } d) + 1$ so that early terms give the part you want to subtract.
• For numerical estimates with $(1 + h)^n$ where $h$ is small, the first three or four terms are usually sufficient.
• For irrational expressions like $(\sqrt{a} + b)^n$, pair with $(\sqrt{a} - b)^n$ to extract the integer part.
• Insight. A modest binomial expansion replaces a tedious calculation. Always try the binomial theorem first when you see $a^n$ with $a$ slightly off from a round number.