Definition D1
(a+b)ⁿ means the product of n copies of (a+b).
Proof.
(1)(a+b)¹ = a + bconvention
(2)(a+b)^(k+1) = (a+b)ᵏ (a+b)convention
∎
Definition D2
The number of k-element subsets of a set with n elements is denoted nCk.
Proof.
A subset has no positions. Only which elements it contains determines a subset.convention
∎
Definition D3
An assignment of either a or b to each of the n positions 1, …, n is called a choice f of length n, and the product of the assigned values is T(f) = f(1)f(2)⋯f(n).
Proof.
(1)Position i corresponds to the i-th factor of (a+b)ⁿ.convention, D1
(2)Two choices that differ at even one position are distinct choices.convention
∎
Lemma L1
For every natural number n, (a+b)ⁿ equals the sum of the products T(f) over all choices f of length n.
Proof.
(1)The only choices of length 1 are picking a and picking b.D3
(2)The sum of their products is a + b, and (a+b)¹ = a + b, so P(1) holds.(1), D1
(3)Assume P(k). That is, (a+b)ᵏ = ΣT(f), the sum taken over all choices of length k.assumption
(4)(a+b)^(k+1) = (a+b)ᵏ (a+b)D1
(5) = (ΣT(f))(a+b)(3), (4), E
(6) = Σ T(f)(a+b)(5), A1, A4
(7) = Σ (T(f)a + T(f)b)(6), A1
(8)T(f)a is the product of the choice of length k+1 obtained by appending a to f as the last position, and T(f)b is the product of the one obtained by appending b.(7), D3, A3
(9)Every choice of length k+1 arises exactly once this way from its first k positions and its last position, so the sum in (7) is the sum over all such choices. That is, P(k+1) holds.(7), (8), A4, A5
(10)P(1) holds and P(k) ⟹ P(k+1), so the statement holds for every n.(2), (9), A6
∎
Lemma L2
Among choices of length n, exactly nCk of them pick b exactly k times, and each of their products is aⁿ⁻ᵏbᵏ.
Proof.
(1)To a choice f, associate the set B(f) = {i : f(i) = b}.D3
(2)If two choices differ, they differ at some position, so B(f) differs as well.(1), D3
(3)Conversely, for each subset B of {1, …, n} there is a choice that picks b exactly at those positions.(1), D3
(4)Therefore f ↦ B(f) is a bijection onto the collection of all subsets.(2), (3)
(5)The choices that pick b exactly k times are those with |B(f)| = k, and their number is nCk, the number of k-element subsets.(4), A7, D2
(6)The product of such a choice multiplies a a total of n−k times and b a total of k times, so rearranging gives aⁿ⁻ᵏbᵏ(5), D3, A2, A3
∎
Theorem T1
(a+b)ⁿ = nC0 aⁿ + nC1 aⁿ⁻¹b + ⋯ + nCn bⁿ
Proof.
(1)(a+b)ⁿ is the sum of the products of all choices of length n.L1
(2)For each choice, the number of times k it picks b is exactly one of 0 through n, so it belongs to exactly one group.D3
(3)Every term in group k is aⁿ⁻ᵏbᵏ, and there are nCk of them.(2), L2
(4)Adding the same thing nCk times gives nCk · aⁿ⁻ᵏbᵏ(3), A9
(5)Collecting the sum by groups gives (a+b)ⁿ = Σ nCk aⁿ⁻ᵏbᵏ (k = 0, …, n)(1), (2), (4), A4, A5
∎
Corollary C
For k with 1 ≤ k ≤ n, nCk + nC(k−1) = (n+1)Ck
Proof.
(1)In a set X with n+1 elements, fix one element x.assumption
(2)Divide the k-element subsets of X into those not containing x and those containing x. The two collections are disjoint and together exhaust the whole.(1), D2
(3)Those not containing x are the k-element subsets of the remaining n elements, so there are nCk of them.(2), D2
(4)Those containing x are in bijection, via S ↦ S∖{x}, with the (k−1)-element subsets of the remaining n elements, so there are nC(k−1) of them.(2), A7, D2
(5)nCk + nC(k−1) = (n+1)Ck(3), (4), A8, D2
(6)Since the coefficients of (a+b)ⁿ are nCk, this relation is also a relation among coefficients. That each number in Pascal's triangle is the sum of the two above it is exactly (5).(5), T1
∎