Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 Putnam B Problems/Problem 2"

(Created page with "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...")
 
(→‎See Also)
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
==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 \} \).
 
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
 +
<cmath>
 +
f_n(z) = n + (n-1)z + (n-2)z^2 + \dots + z^{n-1},
 +
</cmath>
 +
we want to show \( f_n(z) \neq 0 \) for all \( |z| \leq 1 \).
 +
 +
Rewrite \( f_n(z) \) as
 +
<cmath>
 +
f_n(z) = \sum_{k=0}^{n-1} (n-k)z^k.
 +
</cmath>
 +
Multiply by \( 1-z \):
 +
<cmath>
 +
(1-z)f_n(z) = \sum_{k=0}^{n-1} (n-k)z^k - \sum_{k=0}^{n-1} (n-k)z^{k+1}.
 +
</cmath>
 +
Shift index in the second sum:
 +
<cmath>
 +
= n + \sum_{k=1}^{n-1} (n-k)z^k - \sum_{k=1}^{n} (n-(k-1))z^k.
 +
</cmath>
 +
Write out terms:
 +
<cmath>
 +
= n + \sum_{k=1}^{n-1} (n-k)z^k - \sum_{k=1}^{n} (n-k+1)z^k.
 +
</cmath>
 +
Combine sums for \( k=1 \) to \( n-1 \):
 +
<cmath>
 +
= n + \sum_{k=1}^{n-1} [(n-k) - (n-k+1)]z^k - (n-n+1)z^n,
 +
</cmath>
 +
which simplifies to
 +
<cmath>
 +
= n + \sum_{k=1}^{n-1} (-1)z^k - z^n = n - \sum_{k=1}^{n} z^k.
 +
</cmath>
 +
So
 +
<cmath>
 +
(1-z)f_n(z) = n - \frac{z(1-z^n)}{1-z} \quad \text{if } z \neq 1.
 +
</cmath>
 +
Multiply both sides by \( 1-z \):
 +
<cmath>
 +
(1-z)^2 f_n(z) = n(1-z) - z(1-z^n).
 +
</cmath>
 +
Suppose \( f_n(z) = 0 \) with \( |z| \leq 1 \) and \( z \neq 1 \). Then
 +
<cmath>
 +
n(1-z) = z(1-z^n).
 +
</cmath>
 +
Rearranged:
 +
<cmath>
 +
n = \frac{z(1-z^n)}{1-z}.
 +
</cmath>
 +
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==
 +
 +
[[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}}

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},\] 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.\] 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}.\] 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.\] Write out terms: \[= n + \sum_{k=1}^{n-1} (n-k)z^k - \sum_{k=1}^{n} (n-k+1)z^k.\] 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,\] which simplifies to \[= n + \sum_{k=1}^{n-1} (-1)z^k - z^n = n - \sum_{k=1}^{n} z^k.\] So \[(1-z)f_n(z) = n - \frac{z(1-z^n)}{1-z} \quad \text{if } z \neq 1.\] Multiply both sides by \( 1-z \): \[(1-z)^2 f_n(z) = n(1-z) - z(1-z^n).\] Suppose \( f_n(z) = 0 \) with \( |z| \leq 1 \) and \( z \neq 1 \). Then \[n(1-z) = z(1-z^n).\] Rearranged: \[n = \frac{z(1-z^n)}{1-z}.\] 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

2018 Putnam B Entire Test

2018 Putnam B Problem 1

2018 Putnam B Problem 3

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_Putnam_B_Problems/Problem_2&oldid=258248"