Read through concept notes with worked explanations and diagrams, chapter by chapter.
Tip: use←→to switch concepts
Concept 06 / 07Binomial Theorem
Properties of Binomial Coefficients and Series Summation
Sums of coefficients by substitution (x = 1, -1, roots of unity), even and odd coefficient sums, sums weighted by r or 1/(r + 1) via differentiation and integration, Vandermonde's identity for sums of products, and choosing the right technique.
Write Cr=(rn) and start from (1+x)n=C0+C1x+C2x2+⋯+Cnxn. Almost every identity comes from one of four operations on this equation: substitute a value, differentiate, integrate, or multiply two expansions and compare coefficients.
Substitution.
x=1: C0+C1+⋯+Cn=2n.
x=−1: C0−C1+C2−⋯+(−1)nCn=0 (for n≥1).
Adding and subtracting: C0+C2+C4+⋯=C1+C3+C5+⋯=2n−1.
x=ω (a cube root of unity) extracts sums over every third coefficient; x=i separates the sums over r≡0,1,2,3(mod4). For example, C0+C3+C6+⋯=31(2n+(1+ω)n+(1+ω2)n)=31(2n+2cos3nπ).
Differentiation, for sums weighted by r. Differentiating gives n(1+x)n−1=∑rrCrxr−1. At x=1: ∑rCr=n2n−1. At x=−1: ∑(−1)r−1rCr=0 for n≥2. For ∑r2Cr, multiply by x before differentiating again, or use r2=r(r−1)+r and ∑r(r−1)Cr=n(n−1)2n−2; this gives ∑r2Cr=n(n+1)2n−2. An alternative to calculus is the absorption identity rCr=n(r−1n−1), which turns ∑rCr into n∑(r−1n−1)=n2n−1 directly.
Integration, for sums weighted by r+11. Integrate from 0 to 1: ∫01(1+x)ndx=n+12n+1−1=∑r+1Cr. Integrating from −1 to 0 or 0 to −1 gives alternating versions: ∑r+1(−1)rCr=n+11. Again there is a non-calculus route: r+1Cr=n+11(r+1n+1).
Products of coefficients (Vandermonde). Comparing the coefficient of xk on both sides of (1+x)m(1+x)n=(1+x)m+n gives
∑j(jm)(k−jn)=(km+n).
Special cases: C02+C12+⋯+Cn2=(n2n) (use (jn)=(n−jn) and take k=n). C0Cr+C1Cr+1+⋯+Cn−rCn=(n−r2n). The alternating version C02−C12+C22−⋯ comes from (1−x)n(1+x)n=(1−x2)n: it equals 0 for odd n and (−1)n/2(n/2n) for even n.
Choosing a technique. Look at the general term of the sum. A factor r (or a polynomial in r) suggests differentiation or absorption. A factor r+11 (or r+k1) suggests integration. A product of two binomial coefficients whose lower indices add to a constant suggests Vandermonde. A pattern such as every other or every third coefficient suggests substituting roots of unity.
Key Takeaways:
- ∑Cr=2n; even-index sum = odd-index sum =2n−1.
- ∑rCr=n2n−1; ∑r(r−1)Cr=n(n−1)2n−2; ∑r2Cr=n(n+1)2n−2.
- ∑r+1Cr=n+12n+1−1; ∑r+1(−1)rCr=n+11.
- Vandermonde: ∑j(jm)(k−jn)=(km+n); ∑Cr2=(n2n).
- rCr=n(r−1n−1) and r+1Cr=n+11(r+1n+1) avoid calculus.
- Roots of unity filter coefficients by residue class of r.
- Pitfall: in ∑CrCr+k, the lower indices must be arranged to add to a constant before applying Vandermonde.
Brain-Teaser 1: Evaluate S=∑r=0n(r+1)Cr and T=∑r=0n(r+1)(r+2)Cr.
Solution: S=∑rCr+∑Cr=n2n−1+2n=(n+2)2n−1. For T, apply the absorption step twice: r+1Cr=n+11(r+1n+1) and r+21(r+1n+1)=n+21(r+2n+2). So T=(n+1)(n+2)1∑r=0n(r+2n+2)=(n+1)(n+2)2n+2−1−(n+2)=(n+1)(n+2)2n+2−n−3. The missing terms (0n+2) and (1n+2) must be subtracted from 2n+2, which is the step most often forgotten.
Brain-Teaser 2: Find C0C2+C1C3+C2C4+⋯+Cn−2Cn.
Solution: Rewrite the second factor using symmetry: Cr+2=(n−r−2n). Then each term is (rn)(n−2−rn), whose lower indices add to n−2. By Vandermonde, the sum is (n−22n). The whole trick is to flip one coefficient so that the lower indices sum to a constant, which is the pattern Vandermonde needs.
Brain-Teaser 3: Find C0−C2+C4−C6+⋯ for n=10.
Solution: Substitute x=i: (1+i)10=∑Crir. The real part of the right side is C0−C2+C4−C6+C8−C10. The left side is (2eiπ/4)10=32ei⋅10π/4=32eiπ/2=32i, whose real part is 0. So the sum is 0. (Check: 1−45+210−210+45−1=0.) The imaginary part gives C1−C3+C5−C7+C9=32. Complex substitutions filter coefficients by the remainder of r modulo 4.
