8. Counting, induction and the binomial theorem

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$.

Learning goals and definitions

Count ordered and unordered selections, prove the finite binomial theorem, and connect its coefficients to identities. Let $n! =1\cdot2\cdots n$ for positive integers and define $0!=1$. For integers $0\le k\le n$, the binomial coefficient

$$\binom nk=\frac{n!}{k!(n-k)!}$$

counts $k$-element subsets of an $n$-element set. To see the count, first choose an ordered list of $k$ different elements in $n(n-1)\cdots(n-k+1)$ ways; each subset appears in exactly $k!$ orders. Define $\binom nk=0$ for integers outside $0\le k\le n$.

The multiplication principle counts a multi-step construction by multiplying numbers of choices when each stage has the stated number of continuations. The addition principle adds disjoint alternatives. If alternatives overlap, adding them counts some outcomes twice; this is why inclusion–exclusion begins with $|A\cup B|=|A|+|B|-|A\cap B|$ for finite sets.

Theorem: Pascal's identity and the binomial theorem

For integers $n\ge0$,

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

The polynomial identity holds for all real or complex $a,b$.

Proof. To choose $k$ elements from a set with one distinguished element, split into selections that contain it (choose $k-1$ from the other $n$) and selections that do not (choose $k$ from those $n$). The classes are disjoint and exhaustive, proving Pascal's identity, including boundary cases with the zero convention. The binomial theorem holds at $n=0$. Assuming it for $n$, multiply by $a+b$. In the coefficient of $a^{n+1-k}b^k$, the two contributions are $\binom nk$ and $\binom n{k-1}$; Pascal's identity makes their sum $\binom{n+1}k$. This proves the induction step and therefore every nonnegative integer case.

The theorem is finite. Replacing $n$ by a noninteger produces an infinite binomial series, which requires a convergence theorem not supplied by this induction proof.

Worked examples

A coefficient with a negative term. In $(2x-1)^5$, the coefficient of $x^3$ uses three copies of $2x$ and two of $-1$, so it is $\binom53 2^3(-1)^2=80$. Counting the number of $x$ factors before substituting into the formula prevents an exponent reversal.

An identity from substitution. Putting $a=b=1$ gives $\sum_{k=0}^n\binom nk=2^n$, the number of all subsets. For $n\ge1$, putting $a=1,b=-1$ gives $\sum_{k=0}^n(-1)^k\binom nk=0$, so there are equally many even- and odd-sized subsets. A combinatorial proof toggles membership of one fixed element, pairing each even subset with an odd one.

Selection without ordering. From seven people, a three-person committee can be chosen in $\binom73=35$ ways. Assigning president, secretary and treasurer instead gives $7\cdot6\cdot5=210$, because the roles distinguish different orders.

Graded practice

1. Foundation. Compute $\binom82$ and explain what it counts.
2. Core. Find the coefficient of $x^4$ in $(1-3x)^6$.
3. Core. A five-card hand is selected from a standard 52-card deck. How many hands contain exactly two aces? State why the factors multiply.
4. Proof. Prove $\sum_{k=0}^n k\binom nk=n2^{n-1}$ for $n\ge1$ by counting a subset together with one distinguished member.

Full solutions

1. $\binom82=8\cdot7/2=28$, the number of unordered pairs of distinct elements of an eight-element set.
2. Choose four copies of $-3x$ and two copies of $1$. The coefficient is $\binom64(-3)^4=15\cdot81=1215$.
3. Choose two of the four aces and three of the 48 non-aces: $\binom42\binom{48}3$. Every resulting hand has a unique ace part and non-ace part; each allowed choice of one can accompany every allowed choice of the other. This establishes the product count without assuming a probability model.
4. For each size $k$, there are $\binom nk$ subsets and $k$ choices of distinguished member, giving the left side. Alternatively choose that member first in $n$ ways and then any subset of the other $n-1$ elements in $2^{n-1}$ ways. Both count exactly the same pairs, proving the identity.

Summary and term definitions

A permutation is an ordered selection; a combination is an unordered selection. Induction proves a base case and an implication from each case to the next, not merely several examples. A coefficient is the scalar multiplying a specified power. Finite binomial expansions follow from exact counting or induction; any infinite extension needs separate analysis of convergence and remainder.