Complex Numbers & Binomial Theorem
Learning Objectives
- Understand the fundamental concepts of Complex Numbers & Binomial Theorem
- Apply key formulas and techniques to solve problems
- Practice with exam-level questions to build speed and accuracy
1. Introduction to Complex Numbers and Their Geometric Representation
1.1 Definition and Algebraic Form
A complex number is an ordered pair of real numbers written in the form z = a + bi, where a and b are real numbers and i denotes the imaginary unit satisfying i² = –1. The real part of z is Re(z) = a and the imaginary part is Im(z) = b. This algebraic form allows addition, subtraction, multiplication and division to be performed using the familiar rules of arithmetic together with the defining relation i² = –1. For example, the product of (a + bi) and (c + di) is (ac – bd) + (ad + bc)i. The ability to treat i as a number extends the real number system to a field that is algebraically closed, meaning every non‑constant polynomial with complex coefficients has a root in the complex numbers.
1.2 The Argand Plane
The geometric interpretation of complex numbers is provided by the Argand plane (also called the complex plane). In this plane the horizontal axis represents the real part and the vertical axis represents the imaginary part. The point (a, b) corresponds to the complex number a + bi. This representation converts algebraic operations into geometric transformations. Adding two complex numbers corresponds to the vector addition of their position vectors, while multiplication by a real scalar stretches or shrinks the vector without rotating it.
1.3 Modulus and Argument
The distance of the point (a, b) from the origin is called the modulus (or absolute value) of z and is denoted |z|. By the Pythagorean theorem, |z| = √(a² + b²). The angle measured from the positive real axis to the line joining the origin to the point is the argument of z, written arg(z). The argument is defined up to multiples of 2π and is usually taken in the principal range (–π, π]. Using polar coordinates, any non‑zero complex number can be expressed as z = |z|(cos θ + i sin θ), where θ = arg(z). This polar form is indispensable for understanding multiplication, division, and exponentiation of complex numbers because the moduli multiply and the arguments add.
1.4 Consequences of the Polar Form
When two complex numbers z₁ = r₁(cos θ₁ + i sin θ₁) and z₂ = r₂(cos θ₂ + i sin θ₂) are multiplied, the product is z₁z₂ = r₁r₂[cos(θ₁+θ₂) + i sin(θ₁+θ₂)]. Thus multiplication corresponds to scaling by the product of the moduli and rotating by the sum of the arguments. Division works analogously: z₁ / z₂ = (r₁/r₂)[cos(θ₁–θ₂) + i sin(θ₁–θ₂)]. These facts lead directly to De Moivre’s theorem, which states that for any integer n, (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ. De Moivre’s theorem is the bridge between complex numbers and the binomial theorem, as it provides a compact way to expand powers of complex numbers in trigonometric form.
2. Roots of Unity and Their Algebraic Structure
2.1 Definition of n‑th Roots of Unity
An n‑th root of unity is any complex number ζ satisfying ζⁿ = 1. The equation zⁿ – 1 = 0 has exactly n distinct solutions in the complex plane, a consequence of the Fundamental Theorem of Algebra. Using the polar representation of 1 as 1 = 1·(cos 0 + i sin 0), the solutions are obtained by dividing the full angle 2π into n equal parts. Hence the roots are ζ_k = cos(2πk/n) + i sin(2πk/n) for k = 0, 1, …, n–1. These points lie on the unit circle and are equally spaced, forming the vertices of a regular n-gon inscribed in the circle.
2.2 Primitive Roots and Their Properties
A root ζ is called primitive if its smallest positive integer exponent that yields 1 is exactly n. In other words, ζⁿ = 1 but ζ^k ≠ 1 for any 0 < k < n. The primitive roots are precisely those ζ_k for which k and n are coprime. The set of all primitive n‑th roots forms a multiplicative group of order φ(n), where φ denotes Euler’s totient function. This group structure is useful when solving cyclotomic equations and when applying the binomial theorem to expressions such as (x – ζ).
2.3 Applications of Roots of Unity
Roots of unity appear in many areas of mathematics. In polynomial factorisation, the factor xⁿ – 1 can be written as the product of linear factors (x – ζ_k). In discrete Fourier analysis, the complex exponentials used as basis functions are precisely the roots of unity, enabling the conversion between time and frequency domains. Moreover, the symmetry of roots of unity simplifies the evaluation of certain trigonometric sums, because the sum of all n‑th roots is zero, a fact that follows from the geometric series formula applied to the complex exponential form.
2.4 Comparison of Primitive and Non‑Primitive Roots
| Aspect | Primitive Roots | Non‑Primitive Roots |
|---|---|---|
| Order | Exactly n | Divides n, less than n |
| Number | φ(n) | n – φ(n) |
| Coprime Index | k such that gcd(k,n)=1 | k with gcd(k,n)>1 |
| Group Generated | Full cyclic group of order n | Proper subgroup |
3. Binomial Theorem for Real and Complex Exponents
3.1 Statement of the Binomial Theorem
The binomial theorem provides a formula for expanding powers of a sum: for any integer n ≥ 0, (a + b)ⁿ = Σk=0n C(n,k) an‑k bk, where C(n,k) = n! / [k!(n‑k)!] are the binomial coefficients. The theorem holds not only for real numbers a and b but also when they are complex, because the algebraic proof relies solely on the distributive law and the definition of factorial, both of which are valid in the complex field.
3.2 Derivation Using Induction
One common proof proceeds by mathematical induction on n. The base case n = 1 is trivial: (a + b)¹ = a + b. Assuming the formula holds for some n, multiply both sides by (a + b) and rearrange the resulting double sum. The combinatorial identity C(n,k) + C(n,k‑1) = C(n+1,k) emerges naturally, completing the inductive step. Because the proof uses only algebraic manipulation, it remains valid when a and b are complex numbers such as i or a root of unity.
3.3 Binomial Expansion with Complex Bases
When the base involves complex numbers, the expansion yields terms that combine real and imaginary parts. For instance, expanding (1 + i)⁴ gives 1 + 4i + 6i² + 4i³ + i⁴. Substituting i² = –1, i³ = –i, and i⁴ = 1 simplifies the expression to a purely real number, illustrating how complex conjugate pairs often cancel imaginary contributions. This phenomenon is central to many competition problems where a seemingly messy complex expansion reduces to an integer.
3.4 Connection with De Moivre’s Theorem
De Moivre’s theorem can be regarded as a special case of the binomial theorem applied to the polar form (cos θ + i sin θ)ⁿ. Expanding using the binomial coefficients and then separating real and imaginary parts reproduces the identities cos nθ = Σk even (–1)k/2 C(n,k) cosn‑kθ sinkθ and sin nθ = Σk odd (–1)(k‑1)/2 C(n,k) cosn‑kθ sinkθ. Thus the binomial theorem provides a systematic route to multiple‑angle formulas, which are frequently tested in examinations.
3.5 Comparison of Real‑Coefficient and Complex‑Coefficient Expansions
| Feature | Real Coefficients | Complex Coefficients |
|---|---|---|
| Term Types | All terms are real | Terms may be real, imaginary, or mixed |
| Cancellation | Rarely occurs | Often, due to i² = –1 |
| Use in Trigonometry | Limited | Direct link via De Moivre |
| Symmetry | Symmetric binomial coefficients only | Symmetry plus conjugate pairing |
4. Worked Example and Exam‑Day Tip
Find the value of (1 + i)⁸ and express the answer in the form a + bi.
We first note that 1 + i = √2 (cos π/4 + i sin π/4). Using De Moivre’s theorem, (1 + i)⁸ = (√2)⁸ [cos(8·π/4) + i sin(8·π/4)] = 2⁴ [cos 2π + i sin 2π] = 16·(1 + i·0) = 16. Hence the imaginary part vanishes and the result is 16 + 0i. Alternatively, expanding with the binomial theorem gives (1 + i)⁸ = Σk=08 C(8,k) ik. Grouping even and odd powers of i and using i² = –1 leads to the same simplification: all imaginary contributions cancel, leaving 16. Therefore the final answer is 16 + 0i.
When a problem involves powers of a complex number of the form a + bi, first check whether the number lies on the unit circle. If |a + bi| = 1, rewrite it in polar form cos θ + i sin θ and apply De Moivre’s theorem; this usually reduces the computation to evaluating a simple trigonometric angle, saving time and avoiding lengthy binomial expansions.
5. Summary and Further Connections
5.1 Key Formulae to Memorise
- Modulus: |a + bi| = √(a² + b²)
- Argument: arg(a + bi) = tan⁻¹(b/a) (adjusted for quadrant)
- Polar Form: a + bi = |z|(cos θ + i sin θ)
- De Moivre: (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ
- Binomial Theorem: (a + b)ⁿ = Σ C(n,k) an‑k bk
- n‑th Roots of Unity: ζ_k = cos(2πk/n) + i sin(2πk/n)
5.2 How These Topics Interlink
The Argand plane provides a visual language that translates algebraic operations into geometric motions. Modulus and argument turn multiplication into scaling and rotation, which in turn makes De Moivre’s theorem a natural consequence of the binomial expansion applied to polar form. Roots of unity are simply the points on the unit circle that return to the identity after a finite number of rotations; their algebraic properties stem from the same binomial principles that govern general powers. Consequently, mastery of complex numbers, their geometric interpretation, and the binomial theorem equips a student to tackle a wide range of problems, from solving polynomial equations to evaluating trigonometric sums.
5.3 Typical Examination Focus
Students are frequently asked to:
- Convert a complex number between rectangular and polar forms.
- Compute modulus and argument, and use them to multiply or divide complex numbers.
- Find all n‑th roots of unity and identify primitive roots.
- Apply De Moivre’s theorem to evaluate powers and extract real or imaginary parts.
- Expand expressions using the binomial theorem where the terms involve i or roots of unity, and simplify the result.
- Derive multiple‑angle formulas from the binomial expansion of (cos θ + i sin θ)ⁿ.
5.4 Suggested Further Reading
To deepen understanding, students should explore the following concepts after completing this lesson: the geometric interpretation of complex conjugation, the proof of Euler’s formula eiθ = cos θ + i sin θ, and the role of cyclotomic polynomials in number theory. These topics reinforce the unity of algebraic and geometric viewpoints that underlie the study of complex numbers.
Geometric Interpretation of Complex Powers and Roots
On the Argand plane a complex number z = r(cos θ + i sin θ) is represented by the point with polar coordinates (r, θ). Raising z to an integer power n multiplies the modulus by rⁿ and rotates the argument by nθ, so the image of zⁿ lies on a logarithmic spiral when r ≠ 1 and on a circle when r = 1. This geometric picture explains why the n‑th roots of a non‑zero complex number are the vertices of a regular n‑gon centred at the origin: each root has modulus r¹ᐟⁿ and arguments (θ + 2πk)/n for k = 0,…,n‑1. The equal angular spacing of 2π/n follows directly from the periodicity of the exponential function. When r = 1 the roots lie on the unit circle, and the polygon is inscribed in that circle. The mapping w = zⁿ is conformal everywhere except at the origin; angles are multiplied by n, which is why a small sector of angle Δθ near z is stretched to a sector of angle nΔθ near zⁿ. This property underlies many contest problems that ask for the area or perimeter of the polygon formed by the roots, because the side length can be expressed as 2 r¹ᐟⁿ sin(π/n). Moreover, the product of all n roots equals (−1)ⁿ⁻¹ z, a consequence of Vieta’s formulas applied to the polynomial wⁿ − z = 0. Visualising the rotation and scaling simultaneously helps to avoid sign errors when converting between rectangular and polar forms, especially for negative real bases where the principal argument is π rather than 0.
An important subtlety arises for non‑integer powers. The function z^α with α ∉ ℤ is multi‑valued because the argument can be increased by any integer multiple of 2π before multiplication by α. The principal branch is obtained by restricting the argument to (−π, π]; other branches differ by a factor e2πiαk. In examinations this multi‑valuedness often appears in questions that ask for “all values of (1 + i)1/2” – the answer consists of two points symmetric about the origin. Recognising that the set of values forms a rotated and scaled copy of the original number’s argument set is a fast way to write down the answer without solving quadratic equations.
Generalised Binomial Series for Complex Exponents
The binomial theorem (a + b)ⁿ = Σk=0n C(n,k) an−k bk is originally proved for non‑negative integer n by induction. When n is an arbitrary complex number α, the finite sum becomes an infinite series (1 + x)^α = Σk=0∞ C(α,k) xk where the generalised binomial coefficient is defined as C(α,k) = α(α−1)…(α−k+1)/k!. This series converges absolutely for |x| < 1 and conditionally on the boundary |x| = 1 depending on Re(α). The radius of convergence is exactly 1 because the ratio test gives limk→∞ |C(α,k+1)/C(α,k)| = 1. For α a negative integer the series terminates after |α|+1 terms, reproducing the familiar finite expansion. When α is a non‑integer rational number the series provides a way to compute fractional powers of complex numbers without extracting roots explicitly; for example (1 + i)1/2 can be expanded by writing 1 + i = √2 eiπ/4 and then applying the series to (1 + (√2 eiπ/4−1))1/2, though in practice the polar method is simpler. The generalised coefficients satisfy the same recurrence C(α,k+1) = C(α,k)·(α−k)/(k+1), which is useful for generating terms recursively in programming contests. A classic application is the derivation of the Taylor series for (1 − x)−1/2 = Σk=0∞ C(2k,k) (x/4)k, which appears in the evaluation of integrals such as ∫₀¹ dx/√(1−x²) = π/2. In the complex plane the series also converges on the arc of the unit circle where Re(α) > −1, a fact that can be used to sum certain trigonometric series by setting x = eiθ and separating real and imaginary parts.
Cyclotomic Polynomials and Factorisation of xⁿ − 1
The polynomial xⁿ − 1 splits completely over the complex numbers as ∏k=0n−1 (x − ζ_n^k) where ζ_n = e2πi/n is a primitive n‑th root of unity. Grouping factors according to the order of each root yields the factorisation xⁿ − 1 = ∏d|n Φ_d(x), where Φ_d(x) is the d‑th cyclotomic polynomial whose roots are precisely the primitive d‑th roots of unity. Each Φ_d(x) is monic, has integer coefficients, and is irreducible over ℚ. The degree of Φ_d is φ(d), Euler’s totient function. For example Φ₁(x) = x − 1, Φ₂(x) = x + 1, Φ₃(x) = x² + x + 1, Φ₄(x) = x² + 1, Φ₅(x) = x⁴ + x³ + x² + x + 1, and Φ₆(x) = x² − x + 1. The coefficients of cyclotomic polynomials are known to be −1, 0, or 1 for n < 105; the first coefficient with absolute value 2 appears in Φ₁₀₅(x). This fact is occasionally tested in problems that ask for the coefficient of a specific term in Φ_n(x) for small n. The Möbius inversion formula gives an explicit expression Φ_n(x) = ∏d|n (x^d − 1)μ(n/d) where μ is the Möbius function. Using this formula one can compute Φ_n(x) recursively without finding all roots. In contest problems the identity ∑d|n φ(d) = n is frequently used to deduce the degree of the product of cyclotomic polynomials. Another useful property is that for any integer a, the integer Φ_n(a) divides aⁿ − 1 and is coprime to a^d − 1 for all proper divisors d of n; this underlies many divisibility proofs in number theory.
Chebyshev Polynomials from De Moivre’s Theorem
De Moivre’s theorem (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ can be expanded by the binomial theorem and the real part isolated to obtain cos nθ as a polynomial in cos θ of degree n. These polynomials are the Chebyshev polynomials of the first kind T_n(x) defined by T_n(cos θ) = cos nθ. The recurrence T₀(x) = 1, T₁(x) = x, Tn+1(x) = 2x T_n(x) − Tn−1(x) follows directly from the cosine addition formula. The explicit binomial expression is T_n(x) = Σk=0⌊n/2⌋ (−1)^k n/(n−k) C(n−k, k) (2x)n−2k. The leading coefficient is 2n−1 for n ≥ 1. Chebyshev polynomials of the second kind U_n(x) satisfy sin (n+1)θ / sin θ = U_n(cos θ) and obey the same recurrence with U₀ = 1, U₁ = 2x. Both families are orthogonal on [−1, 1] with respect to the weights (1−x²)−1/2 and (1−x²)1/2 respectively, a fact that appears in approximation theory but rarely in standard examinations. In competitive problems the most common use is to express cos nθ or sin nθ as a polynomial in cos θ or sin θ, which then allows the evaluation of sums like Σk=0n cos(kθ) by using the formula for a geometric series in the complex plane and taking the real part. The identity T_n(x) = ( (x + √(x²−1))^n + (x − √(x²−1))^n ) / 2 provides a closed form that is useful when x > 1, turning trigonometric problems into algebraic ones.
Roots‑of‑Unity Filter for Trigonometric Sums
A powerful technique for evaluating sums of the form Σk=0n−1 f(ζ_n^k) where f is a polynomial or rational function is the roots‑of‑unity filter. The filter states that for any integer m, (1/n) Σk=0n−1 ζ_nkm equals 1 if n divides m and 0 otherwise. This follows from the geometric series formula for the sum of powers of a primitive root. To extract the sum of coefficients of xm in a polynomial P(x) where m runs over a congruence class modulo n, one computes (1/n) Σk=0n−1 ζ_n−km P(ζ_n^k). A classic application is the evaluation of Σk=0⌊n/3⌋ C(n, 3k). Setting P(x) = (1 + x)^n and using the filter with n = 3 gives the sum as (1/3)[2^n + 2 Re((1 + ω)^n)] where ω = e2πi/3. Since 1 + ω = −ω², the expression simplifies to (1/3)[2^n + 2 cos(2πn/3)]. Similar filters with n = 4, 5, 6 produce closed forms for sums of binomial coefficients spaced by 4, 5, or 6. The method extends to trigonometric sums such as Σk=0n−1 cos(kθ) by writing cos(kθ) = (ζ_n^k + ζ_n−k)/2 with ζ_n = eiθ and applying the filter when θ = 2πm/n. In examinations the filter is often disguised as “find the remainder when Σk≡r (mod m) C(N,k) is divided by a prime”, where Lucas’ theorem combines with the filter to give a rapid answer. Mastery of this technique requires comfort with manipulating sums of powers of roots of unity and recognising when a given sum can be expressed as a coefficient extraction problem.
- Assuming the principal argument of a negative real number is 0 instead of π, leading to incorrect polar forms.
- Treating the generalised binomial series as a finite sum when the exponent is not a non‑negative integer.
- Forgetting that cyclotomic polynomials are defined only for positive integers and misapplying the Möbius inversion to non‑integer indices.
- Confusing Chebyshev polynomials of the first and second kind, especially their initial values and recurrence coefficients.
- Applying the roots‑of‑unity filter without verifying that the sum index matches the order of the root used.
- Neglecting the convergence condition |x| < 1 for the generalised binomial series when x lies on the unit circle.
- Overlooking the multi‑valued nature of complex fractional powers and giving only the principal value when all values are required.
These traps highlight the subtle points that differentiate a routine solution from a fully correct one in advanced complex‑number and binomial‑theorem problems.
Complex Logarithm and Multi‑valued Exponentiation
The complex logarithm extends the real logarithm by admitting infinitely many values. For a non‑zero complex number z = r eiθ with r > 0 and θ = Arg(z) the principal argument, the set of all logarithms is log z = ln r + i(θ + 2πk) where k ∈ ℤ. The principal value Log z = ln r + iθ (with −π < θ ≤ π) is a single‑valued branch obtained by restricting the argument to the principal interval. A branch cut, usually placed along the negative real axis, makes Log z continuous on ℂ \ (−∞,0]. Multi‑valued exponentiation is defined by zw = exp(w log z). Because log z has infinitely many values, zw is generally multi‑valued unless w is an integer. For rational w = p/q in lowest terms, zp/q yields exactly q distinct values, corresponding to the q‑th roots of zp. The identity (zw)v = zwv holds only modulo the multi‑valued nature; one must select consistent branches. In examinations, a common task is to find all values of (−1)i or ii. Using log(−1) = iπ + 2πik gives (−1)i = e−π − 2πk, a set of positive real numbers. For ii, log i = iπ/2 + 2πik yields ii = e−π/2 − 2πk. The principal values are e−π and e−π/2 respectively. Understanding branch cuts is essential when integrating functions like Log z along contours that cross the negative real axis; the jump across the cut is 2πi.
Binomial Coefficients with Complex Parameters and the Gamma Function
The binomial coefficient can be extended from integers to arbitrary complex numbers α by the formula (α choose k) = α(α−1)…(α−k+1)/k! for k ∈ ℕ₀. This definition coincides with the classical one when α is a non‑negative integer. Using the Gamma function Γ(z), which satisfies Γ(z+1)=zΓ(z) and Γ(n+1)=n! for integers, the coefficient can be written as (α choose k) = Γ(α+1) / (Γ(k+1) Γ(α−k+1)). This representation is valid for all complex α except negative integers where the Gamma function has poles. The generalized binomial series (1+z)α = Σk=0∞ (α choose k) zk converges absolutely for |z| < 1 and defines the principal branch of (1+z)α (with the cut usually taken along (−∞,−1]). When α is a negative integer, the series terminates and reproduces the finite binomial expansion. For non‑integer α, the series is infinite and provides an analytic continuation of the function. The coefficients satisfy the same recurrence (α choose k) = (α−1 choose k) + (α−1 choose k−1) and the symmetry (α choose k) = (−1)k (k−α−1 choose k). In combinatorial problems, sums such as Σ (−1)k (α choose k) / (k+β) can be evaluated by integrating the binomial series termwise and using the Beta function B(x,y)=Γ(x)Γ(y)/Γ(x+y). For example, ∫₀¹ (1−t)α tβ−1 dt = B(α+1,β) yields closed forms for many alternating sums. The Gamma function also allows the evaluation of products like Πk=1n−1 sin(πk/n) = n/2n−1 via the reflection formula Γ(z)Γ(1−z)=π/sin(πz).
Geometric Transformations in the Argand Plane: Rotation, Scaling, and Inversion
Multiplication by a non‑zero complex constant w = ρ eiφ acts on the Argand plane as a composition of a rotation by φ and a scaling by ρ. Explicitly, z ↦ w z sends r eiθ to ρ r ei(θ+φ). This linear map preserves angles and orientation; it is a similarity transformation. The inverse transformation is multiplication by 1/w. A pure rotation corresponds to |w|=1, i.e. w = eiφ. A pure scaling (homothety) corresponds to w ∈ ℝ+. The map z ↦ z (complex conjugation) reflects the plane across the real axis; it is an anti‑conformal isometry. Inversion in the unit circle is given by z ↦ 1/z (or equivalently z ↦ 1/z followed by conjugation). This map sends a point at distance r from the origin to distance 1/r while preserving the argument; it exchanges the interior and exterior of the unit circle and maps lines and circles to lines or circles. The general Möbius transformation z ↦ (a z + b)/(c z + d) with ad−bc ≠ 0 is a composition of translations, rotations, scalings, and inversions. It maps the extended complex plane (Riemann sphere) onto itself, preserving the set of generalized circles (lines and circles). In competitive problems, one often uses the fact that the image of a line not passing through the origin under z ↦ 1/z is a circle passing through the origin, and vice‑versa. The cross‑ratio (z₁,z₂;z₃,z₄) = (z₁−z₃)(z₂−z₄)/((z₁−z₄)(z₂−z₃)) is invariant under Möbius transformations, providing a powerful tool for proving concyclicity or collinearity of four points.
Applications of Roots of Unity in Polynomial Interpolation and Discrete Fourier Transform
The n‑th roots of unity ωk = e2πi k/n (k=0,…,n−1) form a cyclic group under multiplication. Evaluating a polynomial P(x) of degree < n at these points yields the discrete Fourier transform (DFT) of its coefficient vector. The DFT matrix Fjk = ωjk is unitary up to the factor 1/√n. The inverse transform reconstructs the coefficients via ak = (1/n) Σj=0n−1 P(ωj) ωj−k. This is exactly the Lagrange interpolation formula specialized to the roots of unity. The fast Fourier transform (FFT) computes the DFT in O(n log n) operations by recursively splitting the sum into even and odd indices, exploiting the identity ω2k = ωk2. In examinations, the DFT appears in problems asking for the sum Σ P(ωk) or for the coefficient of xm in a product of polynomials. The convolution theorem states that the DFT of the product of two polynomials (mod xn−1) is the pointwise product of their DFTs. This allows rapid multiplication of polynomials and evaluation of sums like Σk C(n,k) C(m, r−k) by interpreting them as coefficients of (1+x)n(1+x)m. The roots‑of‑unity filter, already discussed, is a special case of the DFT where one extracts coefficients whose indices lie in a fixed congruence class modulo n. For instance, the sum of binomial coefficients C(N, k) with k ≡ r (mod m) equals (1/m) Σj=0m−1 ωm−jr (1+ωmj)N. When N is large, this formula combined with Lucas’ theorem modulo a prime gives an efficient way to compute the sum modulo that prime.
Advanced Combinatorial Identities via the Binomial Theorem and Complex Integration
Many combinatorial sums admit elegant evaluations using contour integrals of rational functions multiplied by powers of (1+z) or (1−z). The key identity is the Cauchy integral formula for coefficients: [zk] f(z) = (1/2πi) ∮ f(z) / zk+1 dz, where the contour encircles the origin. Choosing f(z) = (1+z)n gives the binomial coefficient C(n,k). Sums of the form Σ C(n,k) C(m, r−k) become coefficients of (1+z)n+m and are evaluated by a single integral. More generally, integrals of the type ∮ (1+z)α (1−z)β z−γ dz produce hypergeometric identities. For example, the Chu–Vandermonde identity Σk C(α,k) C(β, n−k) = C(α+β, n) follows from the coefficient of zn in (1+z)α+β. The Beta integral ∫₀¹ ta−1 (1−t)b−1 dt = B(a,b) is recovered by setting z = t/(1−t) in a contour integral around the segment [0,1]. In problems involving alternating sums with harmonic numbers, one uses the generating function −ln(1−z)/(1−z) = Σ Hn zn and integrates termwise. The method of “creative telescoping” often reduces a sum to a contour integral of a rational function whose residues are easy to compute. A classic example is the evaluation of Σk=0n (−1)k C(n,k) / (k+1)2. Writing 1/(k+1)2 = ∫₀¹ ∫₀¹ xk yk dx dy and swapping sum and integrals yields ∫₀¹∫₀¹ (1−xy)n dx dy, which can be evaluated in closed form using Beta functions. Mastery of these techniques requires fluency in switching between discrete sums, generating functions, and complex integrals, and in recognizing when a sum is a coefficient extraction problem.
- Assuming the principal branch of the logarithm when the problem asks for all values of a complex power.
- Applying the generalized binomial series outside its disc of convergence |z| < 1 without analytic continuation.
- Confusing the effect of z ↦ 1/z (inversion plus reflection) with pure inversion z ↦ 1/z.
- Using the roots‑of‑unity filter with an order that does not match the periodicity of the summand.
- Neglecting the contribution of poles on the contour when evaluating coefficient integrals by residues.
- Treating the Gamma function as finite at non‑positive integers, leading to division by zero in binomial coefficient formulas.
- Forgetting that the DFT matrix is unitary only after scaling by 1/√n, which affects Parseval‑type identities.