Problem:
Define a sequence of functions recursively by f1(x)=∣x−1∣ and fn(x)=fn−1(∣x−n∣) for integers n>1. Find the least value of n such that the sum of the zeros of fn exceeds 500,000.
Solution:
We aim to prove by induction that the zeros of the function fn are the integers in the arithmetic sequence a,a+2,a+4,…,a+n(n−1), where a=n−2n(n−1).
Base Case: When n=1, the expression simplifies to 1−21⋅0=1, and the only zero of f1 is 1, which agrees with the given pattern.
Inductive Step: Suppose the result holds for n=m−1≥1. Then the zeros of fm−1 form an arithmetic sequence with common difference 2, starting at a=m−1−2(m−1)(m−2).
Now consider fm. Its zeros are given by the equation ∣x−m∣=k, where k ranges over the nonnegative zeros of fm−1. Each k yields two solutions: x=m−k and x=m+k, so the zeros of fm also form an arithmetic sequence with step size 2.
The greatest zero of fm−1 is:
(m−1)+2(m−1)(m−2)=2m(m−1),
so the smallest and largest zeros of fm are:
m−2m(m−1),m+2m(m−1).
Therefore, the number of zeros of fn is:
2n(n−1)+1.
Since the zeros are symmetric about x=n, their average is n, so the sum of the zeros is:
n⋅(2n(n−1)+1)=2n3−n2+2n.
Let S(n)=2n3−n2+2n=2n(n−2)(n+1).
We want the least n such that S(n)>500,000.
Try n=100:
S(100)=2100⋅98⋅101=990,200.
Try n=101:
S(101)=2101⋅99⋅102=1,020,297.
Thus, the least n such that S(n)>500,000 is 101.
The problems on this page are the property of the MAA's American Mathematics Competitions