Interesting results easily achieved using complex numbers

I was just looking at a calculus textbook preparing my class for next week on complex numbers. I found it interesting to see as an exercise a way to calculate the usual freshman calculus integrals eaxcosbx dx and eaxsinbx dx by taking the real and imaginary parts of the “complex” integral e(a+bi)x dx.

So my question is if you know of other “relatively interesting” results that can be obtained easily by using complex numbers.

It may be something that one can present to engineering students taking the usual calculus sequence, but I’m also interested in somewhat more advanced examples (if they’re available under the condition that the process to get them is somewhat easy, or not too long). Thank you all.

Answer

There are too many examples to count. Let me just mention one that is particularly concrete: how many subsets of an n-element set have a cardinality divisible by 3 (or any positive integer k)? In other words, how do we evaluate

\sum_{k=0}^{\lfloor \frac{n}{3} \rfloor} {n \choose 3k}

in closed form? Although the statement of this problem does not involve complex numbers, the answer does: the key is what is known in high school competition circles as the roots of unity filter and what is known among real mathematicians as the discrete Fourier transform. Starting with the generating function

(1 + x)^n = \sum_{k=0}^n {n \choose k} x^k

we observe that the identity

1 + \omega^k + \omega^{2k} = \begin{cases} 3 \text{ if } 3 \mid k \\\ 0 \text{ otherwise} \end{cases}

where \omega = e^{ \frac{2 \pi i}{3} } is a primitive third root of unity implies that

\sum_{k=0}^{ \lfloor \frac{n}{3} \rfloor} {n \choose 3k} = \frac{(1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n}{3}.

Since 1 + \omega = -\omega^2 and 1 + \omega^2 = – \omega, this gives

\sum_{k=0}^{ \lfloor \frac{n}{3} \rfloor} {n \choose 3k} = \frac{2^n + (-\omega)^n + (-\omega^2)^n}{3}.

This formula can be stated without complex numbers (either by using cosines or listing out cases) but both the statement and the proof are much cleaner with it. More generally, complex numbers make their presence known in combinatorics in countless ways; for example, they are pivotal to the theory of asymptotics of combinatorial sequences. See, for example, Flajolet and Sedgewick’s Analytic Combinatorics.

Attribution
Source : Link , Question Author : Community , Answer Author :
2 revs, 2 users 95%

Leave a Comment