Difference between revisions of "2018 Putnam B Problems/Problem 2"
Pinotation (talk | contribs) (→Solution) |
Pinotation (talk | contribs) (→See Also) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
Let \( n \) be a positive integer, and let \( f_n(z) = n + (n-1)z + (n-2)z^2 + \dots + z^{n-1} \). Prove that \( f_n \) has no roots in the closed unit disk \( \{z \in \mathbb{C}: |z| \leq 1 \} \). | Let \( n \) be a positive integer, and let \( f_n(z) = n + (n-1)z + (n-2)z^2 + \dots + z^{n-1} \). Prove that \( f_n \) has no roots in the closed unit disk \( \{z \in \mathbb{C}: |z| \leq 1 \} \). | ||
| − | ==Solution== | + | ==Solution 1== |
Given | Given | ||
| Line 60: | Line 60: | ||
~Pinotation | ~Pinotation | ||
| + | |||
| + | ==Solution 2 (Fast)== | ||
| + | |||
| + | Write | ||
| + | |||
| + | \( f_n(z) = \sum_{k=0}^{n-1} (n-k) z^k \). | ||
| + | \( f_n(z) = \sum_{k=0}^{n-1} (n-k) z^k = \sum_{k=0}^{n-1} \sum_{j=k}^{n-1} z^k \), | ||
| + | |||
| + | because for each fixed \( k \), the coefficient \( (n-k) \) counts how many \( j \ge k \) there are from \( k \) to \( n-1 \). | ||
| + | |||
| + | Interchange the sums: | ||
| + | |||
| + | \( f_n(z) = \sum_{j=0}^{n-1} \sum_{k=0}^{j} z^k = \sum_{j=0}^{n-1} \frac{1-z^{j+1}}{1-z} = \frac{1}{1-z} \sum_{j=0}^{n-1} (1-z^{j+1}) \). | ||
| + | |||
| + | Simplify the inner sum: | ||
| + | |||
| + | \( \sum_{j=0}^{n-1} 1 = n \), | ||
| + | \( \sum_{j=0}^{n-1} z^{j+1} = z \frac{1-z^n}{1-z} \). | ||
| + | |||
| + | So | ||
| + | |||
| + | \( f_n(z) = \frac{1}{1-z} \left( n - z \frac{1-z^n}{1-z} \right) = \frac{n(1-z) - z(1-z^n)}{(1-z)^2} \). | ||
| + | |||
| + | Suppose \( f_n(z) = 0 \) for some \( |z| \le 1 \) and \( z \ne 1 \), then | ||
| + | |||
| + | \( n(1-z) = z(1-z^n) \). | ||
| + | |||
| + | Rewrite as | ||
| + | |||
| + | \( n = \frac{z(1-z^n)}{1-z} \). | ||
| + | |||
| + | Note that the right side is a sum of \( n \) complex numbers: | ||
| + | |||
| + | \( \frac{z(1-z^n)}{1-z} = z + z^2 + \cdots + z^n \), | ||
| + | |||
| + | which is a geometric sum without the first term (since \( z \ne 1 \)). | ||
| + | |||
| + | For \( |z| \le 1 \), the magnitude of this sum is at most \( n \), and equal to \( n \) only if all terms \( z, z^2, ..., z^n \) lie on the same ray and have magnitude 1. | ||
| + | |||
| + | That requires \( |z| = 1 \) and all terms aligned, so \( z = e^{2\pi i k/n} \) for some integer \( k \). | ||
| + | |||
| + | Check for these roots: | ||
| + | |||
| + | If \( z = 1 \), \( f_n(1) = \frac{n(n+1)}{2} \ne 0 \). | ||
| + | |||
| + | For \( z = e^{2\pi i k/n} \), \( 1-z^n = 0 \), so from the equation \( n(1-z) = z(1-z^n) \) we get \( n(1-z) = 0 \), so \( z = 1 \), contradiction. | ||
| + | |||
| + | Therefore no such root \( z \ne 1 \) exists with \( |z| \le 1 \). | ||
| + | |||
| + | Hence \( f_n(z) \ne 0 \) is not in the closed unit disk. | ||
| + | |||
| + | ~Pinotation | ||
| + | |||
| + | ==See Also== | ||
| + | |||
| + | [[2018 Putnam B Problems|2018 Putnam B Entire Test]] | ||
| + | |||
| + | [[2018 Putnam B Problems/Problem 1|2018 Putnam B Problem 1]] | ||
| + | |||
| + | [[2018 Putnam B Problems/Problem 3|2018 Putnam B Problem 3]] | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Latest revision as of 18:24, 18 August 2025
Problem
Let \( n \) be a positive integer, and let \( f_n(z) = n + (n-1)z + (n-2)z^2 + \dots + z^{n-1} \). Prove that \( f_n \) has no roots in the closed unit disk \( \{z \in \mathbb{C}: |z| \leq 1 \} \).
Solution 1
Given
![\[f_n(z) = n + (n-1)z + (n-2)z^2 + \dots + z^{n-1},\]](http://latex.artofproblemsolving.com/d/1/f/d1f62f8a20858f9ac218b3abe08a16c36abc6897.png)
we want to show \( f_n(z) \neq 0 \) for all \( |z| \leq 1 \).
Rewrite \( f_n(z) \) as
![\[f_n(z) = \sum_{k=0}^{n-1} (n-k)z^k.\]](http://latex.artofproblemsolving.com/b/c/a/bca1fd0ecdfafa40d9d9e02a555e05e895318f5b.png)
Multiply by \( 1-z \):
![\[(1-z)f_n(z) = \sum_{k=0}^{n-1} (n-k)z^k - \sum_{k=0}^{n-1} (n-k)z^{k+1}.\]](http://latex.artofproblemsolving.com/6/4/6/6468023dddb1764fe7fa90f7b4d5bcd930b4d61e.png)
Shift index in the second sum:
![\[= n + \sum_{k=1}^{n-1} (n-k)z^k - \sum_{k=1}^{n} (n-(k-1))z^k.\]](http://latex.artofproblemsolving.com/3/5/9/359311e3061df013ecf042ba734fe0a0f81d4cd5.png)
Write out terms:
![\[= n + \sum_{k=1}^{n-1} (n-k)z^k - \sum_{k=1}^{n} (n-k+1)z^k.\]](http://latex.artofproblemsolving.com/7/1/1/711e9b70aaa0c2d152458fc8e091e18372e34ace.png)
Combine sums for \( k=1 \) to \( n-1 \):
![\[= n + \sum_{k=1}^{n-1} [(n-k) - (n-k+1)]z^k - (n-n+1)z^n,\]](http://latex.artofproblemsolving.com/e/b/7/eb7d59c84a4c5d9c8d4485a38f5f97c0e52c65df.png)
which simplifies to
![\[= n + \sum_{k=1}^{n-1} (-1)z^k - z^n = n - \sum_{k=1}^{n} z^k.\]](http://latex.artofproblemsolving.com/3/9/3/393683270ff33c354b2e8d9e63e25a1ec31e485a.png)
So
![\[(1-z)f_n(z) = n - \frac{z(1-z^n)}{1-z} \quad \text{if } z \neq 1.\]](http://latex.artofproblemsolving.com/b/5/6/b56203fcb1ea8633a1fd28550fdcecaa583f935e.png)
Multiply both sides by \( 1-z \):
![\[(1-z)^2 f_n(z) = n(1-z) - z(1-z^n).\]](http://latex.artofproblemsolving.com/b/c/7/bc7c5d7dfbe494bc0a6af03a46aebb70c9e487ed.png)
Suppose \( f_n(z) = 0 \) with \( |z| \leq 1 \) and \( z \neq 1 \). Then
![\[n(1-z) = z(1-z^n).\]](http://latex.artofproblemsolving.com/2/7/9/279bc651b50a754d64da21b109cf9a481a267adf.png)
Rearranged:
![\[n = \frac{z(1-z^n)}{1-z}.\]](http://latex.artofproblemsolving.com/d/0/8/d08545c50e8678f419a81cbf990415484e47aa57.png)
Consider \( |z| \leq 1 \). If \( |z| = 1 \), then \( |1-z^n| \leq 2 \) and denominator \( |1-z| \) is at most 2, but the right side stays bounded by something less than \( n \) (except at \( z=1 \), excluded). This can't equal \( n \) exactly.
If \( |z| < 1 \), the geometric sum \( \frac{1-z^n}{1-z} \) has magnitude less than \( \frac{1}{1-|z|} \), which is finite but smaller than \( n \). So the equation can't hold for any \( z \neq 1 \).
At \( z=1 \), \( f_n(1) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2} \neq 0 \).
Thus, \( f_n(z) \neq 0 \) for \( |z| \leq 1 \). :-)
~Pinotation
Solution 2 (Fast)
Write
\( f_n(z) = \sum_{k=0}^{n-1} (n-k) z^k \). \( f_n(z) = \sum_{k=0}^{n-1} (n-k) z^k = \sum_{k=0}^{n-1} \sum_{j=k}^{n-1} z^k \),
because for each fixed \( k \), the coefficient \( (n-k) \) counts how many \( j \ge k \) there are from \( k \) to \( n-1 \).
Interchange the sums:
\( f_n(z) = \sum_{j=0}^{n-1} \sum_{k=0}^{j} z^k = \sum_{j=0}^{n-1} \frac{1-z^{j+1}}{1-z} = \frac{1}{1-z} \sum_{j=0}^{n-1} (1-z^{j+1}) \).
Simplify the inner sum:
\( \sum_{j=0}^{n-1} 1 = n \), \( \sum_{j=0}^{n-1} z^{j+1} = z \frac{1-z^n}{1-z} \).
So
\( f_n(z) = \frac{1}{1-z} \left( n - z \frac{1-z^n}{1-z} \right) = \frac{n(1-z) - z(1-z^n)}{(1-z)^2} \).
Suppose \( f_n(z) = 0 \) for some \( |z| \le 1 \) and \( z \ne 1 \), then
\( n(1-z) = z(1-z^n) \).
Rewrite as
\( n = \frac{z(1-z^n)}{1-z} \).
Note that the right side is a sum of \( n \) complex numbers:
\( \frac{z(1-z^n)}{1-z} = z + z^2 + \cdots + z^n \),
which is a geometric sum without the first term (since \( z \ne 1 \)).
For \( |z| \le 1 \), the magnitude of this sum is at most \( n \), and equal to \( n \) only if all terms \( z, z^2, ..., z^n \) lie on the same ray and have magnitude 1.
That requires \( |z| = 1 \) and all terms aligned, so \( z = e^{2\pi i k/n} \) for some integer \( k \).
Check for these roots:
If \( z = 1 \), \( f_n(1) = \frac{n(n+1)}{2} \ne 0 \).
For \( z = e^{2\pi i k/n} \), \( 1-z^n = 0 \), so from the equation \( n(1-z) = z(1-z^n) \) we get \( n(1-z) = 0 \), so \( z = 1 \), contradiction.
Therefore no such root \( z \ne 1 \) exists with \( |z| \le 1 \).
Hence \( f_n(z) \ne 0 \) is not in the closed unit disk.
~Pinotation
See Also
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
