6. Induction and the Binomial Theorem

Learning goals and preparation

A formula can be correct in several examples yet false later. This chapter separates evidence from proof. You will state a proposition with its integer domain, organize a base case and induction step, use the hypothesis only where it is available, and derive and apply the binomial theorem. Chapter 5 supplies finite progressions and algebraic identities; no probability theory is assumed.

6.1 What induction actually proves

Let $P(n)$ be a statement about integers $n\ge n_0$, where $n_0$ is fixed. The principle of mathematical induction says:

1. Prove the base case $P(n_0)$.
2. For an arbitrary integer $k\ge n_0$, assume $P(k)$ and prove $P(k+1)$.
3. Conclude that $P(n)$ holds for every integer $n\ge n_0$.

The assumption in step 2 is the induction hypothesis. It is conditional, not an assumption that the final theorem is already true. The base starts the chain, and the implication extends any valid link to the next.

Here is a justification using the least-element property of the nonnegative integers. If a counterexample existed, there would be a least counterexample $m\ge n_0$. It could not be $n_0$ because of the base case. Then $m-1\ge n_0$ would not be a counterexample, and the induction step would force $P(m)$, a contradiction.

For an arbitrary integer starting index $n_0$, applying the least-element property to the shifted indices $m-n_0\ge0$ justifies the preceding least-counterexample step.

Conversely, ordinary induction on the positive integers implies the least-element property. Suppose a nonempty set $S\subseteq\{1,2,3,\ldots\}$ has no least element. Let $P(n)$ assert that none of $1,\ldots,n$ belongs to $S$. If $1\in S$ it is the least element, so $P(1)$ holds. If $P(k)$ holds but $k+1\in S$, then $k+1$ is the least element of $S$, a contradiction. Thus $P(k)\Rightarrow P(k+1)$. Induction gives $P(n)$ for every positive integer $n$, so $S$ is empty, contradicting its assumed nonemptiness. Hence every nonempty set of positive integers has a least element. Translating indices by $n\mapsto n-n_0+1$ gives the corresponding induction version for any integer starting index $n_0$.

Do not assume what you intend to prove for all integers inside the step. Assume exactly the declared case $P(k)$ (or, in strong induction, the earlier cases explicitly allowed) and derive the next one. Induction establishes a statement for integer indices, not automatically for all real numbers.

Example 1 — a sum with its moving boundary. For every positive integer $n$,

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

At $n=1$ both sides equal $1$. Assume the equality for an arbitrary $k\ge1$. Then

$$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2,$$

which is the desired formula with $n=k+1$. The left sum acquires precisely one new term, not an unexplained new expression.

6.2 Choosing the statement and using the hypothesis

Example 2 — recurrence from repeated additions. Suppose $B_0=0$ and $B_{n+1}=rB_n+c$, where $r,c$ are fixed real numbers. Claim

$$B_n=c\sum_{j=0}^{n-1}r^j\quad(n\ge1).$$

The base $n=1$ gives $B_1=c$. Assuming the formula at $k\ge1$, the recurrence gives

$$B_{k+1}=rc\sum_{j=0}^{k-1}r^j+c =c\left(1+\sum_{j=1}^{k}r^j\right)=c\sum_{j=0}^{k}r^j.$$

Thus the claim holds for all positive integers. Applying Chapter 5's finite geometric sum yields $c(1-r^n)/(1-r)$ when $r\ne1$, while $r=1$ gives $nc$. The induction proof itself never divides by $1-r$, so it covers that exceptional ratio too.

Example 3 — divisibility. For $n\ge1$, $7^n-1$ is divisible by $6$. At $n=1$, it equals $6$. If $7^k-1=6m$ for an integer $m$, then

$$7^{k+1}-1=7(7^k-1)+6=6(7m+1).$$

The multiplier $7m+1$ is an integer. This proves divisibility, rather than merely observing that the expression is even.

A useful strengthening sometimes makes an induction possible. To prove a bound on a recurrence, a weaker-looking target may not carry enough information to the next step. In elementary work, first write $P(k+1)$ explicitly and identify what estimate the recurrence needs. Never replace a failed step by “clearly the pattern continues.”

6.3 Inequalities and the sign of a multiplier

For real $t\ge-1$ and an integer $n\ge1$, Bernoulli's inequality is

$$(1+t)^n\ge1+nt.$$

At $n=1$, equality is immediate. In the step from $k\ge1$, multiplication by $1+t\ge0$ preserves the assumed inequality:

$$(1+t)^{k+1}\ge(1+kt)(1+t) =1+(k+1)t+kt^2\ge1+(k+1)t.$$

The nonnegative remainder proves the next case. The multiplier condition is indispensable; multiplying an inequality by a negative number would reverse its direction. For $t>0$ and $n\ge2$, the inequality is strict because the $k=1$ step already adds a positive $t^2$.

Example 4 — a lower bound, not an equality. A hypothetical quantity has a $2\%$ increase in each of $10$ equal periods. Its multiplier is $1.02^{10}\ge1+10(0.02)=1.2$. Thus the increase is at least $20\%$, not exactly $20\%$. The exact multiplier is given by the compound expression. Induction proves a robust comparison without a decimal approximation.

Failure analysis. The assertion $2^n\ge n^2$ is true at $n=1,2$ but false at $n=3$ because $8<9$. A correct induction proof cannot bridge all $k\ge1$. It does hold for $n\ge4$: at $4$ there is equality, and for $k\ge4$,

$$2^{k+1}\ge2k^2\ge(k+1)^2,$$

since $2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2>0$. The starting range is part of the theorem.

6.4 Binomial coefficients and Pascal's identity

For integers $n\ge0$ and $0\le k\le n$, define

$$\binom nk=\frac{n!}{k!(n-k)!},\qquad 0!=1.$$

It counts $k$-element selections from $n$ distinct objects: there are $n(n-1)\cdots(n-k+1)$ ordered selections, and each unordered selection occurs in $k!$ orders. In particular $\binom n0=\binom nn=1$ and $\binom nk=\binom n{n-k}$.

Pascal's identity, for $1\le k\le n$, is

$$\binom n{k-1}+\binom nk=\binom{n+1}k.$$

To see it without factorial manipulation, distinguish one object among $n+1$. A $k$-element selection either contains it, in which case the other $k-1$ come from $n$, or does not, in which case all $k$ come from $n$. The two alternatives are disjoint and exhaustive. Equivalently, put the two factorial fractions over the common denominator $k!(n+1-k)!$; the numerator factors sum to $k+(n+1-k)=n+1$.

6.5 Deriving the binomial theorem

For a nonnegative integer $n$ and real $a,b$,

$$(a+b)^n=\sum_{k=0}^{n}\binom nk a^{n-k}b^k.$$

Here powers of exponent zero in this polynomial identity represent the constant factor $1$, including at $a=0$ or $b=0$. This is a convention for evaluation of a polynomial, not a claim that every limiting expression $0^0$ has a prescribed value.

Induction proof. At $n=0$ both sides are $1$. Assume the formula for $n$. Multiply it by $a+b$. One part contributes $\binom nk a^{n+1-k}b^k$; the other contributes $\binom n{k-1}a^{n+1-k}b^k$ after shifting the index. Interior terms combine using Pascal's identity, while the two endpoint terms remain $a^{n+1}$ and $b^{n+1}$. The resulting sum is exactly the formula for $n+1$.

There is also a direct interpretation: in the product of $n$ copies of $(a+b)$, a term with $k$ copies of $b$ and $n-k$ copies of $a$ arises by choosing which $k$ factors contribute $b$. There are $\binom nk$ such choices. This explains both the coefficient and the exponents.

The integer condition matters. For example $(1+x)^{1/2}$ is not a two-term polynomial. Infinite binomial expansions require additional convergence theory and are not the finite theorem proved here.

Example 5 — extracting rather than expanding everything. In $(2x-3)^5$, the term involving $x^3$ uses $k=2$ copies of $-3$:

$$\binom52(2x)^3(-3)^2=720x^3.$$

Thus its coefficient is $720$. The sign is positive because the negative term is squared.

Example 6 — a coefficient with an inverse power. In $(x^2+1/x)^6$, $x\ne0$, the general term is $\binom6k x^{12-3k}$. The constant term occurs when $12-3k=0$, so $k=4$ and the constant term is $\binom64=15$. This Laurent expression is not a polynomial in $x$, but the finite binomial theorem applies to its two defined real inputs for each nonzero $x$.

Setting $a=b=1$ gives $\sum_{k=0}^{n}\binom nk=2^n$. For $n\ge1$, setting $a=1,b=-1$ gives $\sum_{k=0}^{n}(-1)^k\binom nk=0$. The latter statement excludes $n=0$, where the sum is $1$.

6.6 Graded exercises

Foundation

1. State the base and induction step needed to prove a proposition for all integers $n\ge3$.
2. Calculate $\binom62$ and $\binom64$, explaining why they agree.
3. Expand $(x+2)^4$ exactly.

Core

4. Prove $1+3+\cdots+(2n-1)=n^2$ for every positive integer $n$.
5. Prove $3^n-1$ is divisible by $2$ for every integer $n\ge1$.
6. Prove $1+2+4+\cdots+2^{n-1}=2^n-1$ by induction, not by quoting the geometric-sum formula.
7. Find the coefficient of $x^2$ in $(3x-1)^5$.
8. Find the constant term of $(x^3-2/x)^8$ for $x\ne0$.

Synthesis

9. A student argues that every $n$-element set of colored counters has just one color: “true for $n=1$; remove the first and then the last counter; the two $n$-element subsets of an $(n+1)$-element set each have one color, so all counters share that color.” Locate the failed step.
10. Show $(1+t)^5\ge1+5t+10t^2$ for $t\ge0$ by the finite binomial theorem. Is the same inequality true for every $-1\le t<0$?
11. Prove by induction that $\sum_{j=1}^{n}j^2=n(n+1)(2n+1)/6$.
12. Use a selection argument to prove $\sum_{k=0}^{n}k\binom nk=n2^{n-1}$ for $n\ge1$.

6.7 Full solutions

1. Verify $P(3)$. Then for an arbitrary integer $k\ge3$, assume $P(k)$ and derive $P(k+1)$. A base at $1$ without the missing connecting cases would not by itself start the chain at $3$.
2. Both are $6!/(2!4!)=15$. Choosing two selected objects is equivalent to choosing the four omitted objects.
3. The coefficients are $1,4,6,4,1$, so $(x+2)^4=x^4+8x^3+24x^2+32x+16$.
4. The base is $1=1^2$. If the first $k$ odd numbers sum to $k^2$, adding the next, $2k+1$, gives $k^2+2k+1=(k+1)^2$.
5. At $1$, $3-1=2$. If $3^k-1=2m$, then $3^{k+1}-1=3(3^k-1)+2=2(3m+1)$, an even integer.
6. At $1$, $1=2-1$. If the sum through $2^{k-1}$ is $2^k-1$, adding $2^k$ gives $2^{k+1}-1$.
7. Choose exactly two copies of $3x$ and three of $-1$. The coefficient is $\binom52 3^2(-1)^3=-90$.
8. The general term is $\binom8k(-2)^k x^{24-4k}$. The exponent is zero at $k=6$, yielding $\binom86(-2)^6=28(64)=1792$.
9. For the step from one to two counters, the two one-counter subsets have no common member. There is no shared counter through which their colors can be equated. The asserted step therefore fails at the first link; later overlaps cannot repair it.
10. The omitted part is $10t^3+5t^4+t^5=t^3(10+5t+t^2)$. It is nonnegative for $t\ge0$. For $-1\le t<0$, $t^3<0$ and $10+5t+t^2>0$, so the proposed inequality is reversed strictly; for example at $t=-1$ it would read $0\ge6$.
11. At $1$, the formula gives $1$. Add $(k+1)^2$ to the assumed sum: $k(k+1)(2k+1)/6+(k+1)^2=(k+1)(2k^2+7k+6)/6=(k+1)(k+2)(2k+3)/6$, exactly the case $k+1$.
12. Count pairs $(S,s)$ where $S$ is a subset of an $n$-element set and $s\in S$ is distinguished. By subset size there are $\sum_k k\binom nk$. Alternatively choose $s$ in $n$ ways and independently choose which of the other $n-1$ elements belong to $S$, in $2^{n-1}$ ways. Equate the two counts.

Summary and transfer

An induction proof has a declared integer range, a starting case and an implication that works at every required link. Divisibility proofs exhibit an integer multiplier; inequality proofs justify the sign of every multiplier. Binomial coefficients count selections, Pascal's identity combines neighboring coefficients, and the finite binomial theorem follows by either multiplication or selection. Coefficient extraction is an exponent problem before it is an arithmetic problem.