An Essayed Answer II
Denote by the sequence of Fibonacci polynomials, which satisfy the recurrence and for all . It is given that there exist unique integers such that for all real . For which integer is maximized?
Note: Full credit is given to the makers of this problem.
The answer is 32.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Denote by F0(x), F1(x), ... the sequence of Fibonacci polynomials, which satisfy the recurrence F0(x) = 1, F1(x) = x, and Fn(x) = xFn−1(x) + Fn−2(x) for all n ≥ 2.1 It is given that there exist integers λ0, λ1, . . ., λ1000 such that 1000 x1000 = λiFi(x) i=0 for all real x. For which integer k is |λk| maximized? Proposed by David Altizio Solution. Replace 1000 with a general n. I claim that for all n ≥ 0 we have that the identity holds true for some value of n. We now split into cases. 1In reality, the indexes are shifted up by one (so e.g. F1(x) = 1), but this interpretation makes the problem statement easier to write since deg Fi(x) = i for all i ≥ 0 ⌊n/2⌋ n n
xn = Fn(x) + (−1)k − Fn−2k(x). k k−1 To prove this, we use mathematical induction. The base case, n = 0, is easy. For the inductive step, assume k=1 1275
• CASE 1: n is odd. Note that multiplying both sides of the equality by x and using the definition of the Fibonacci polynomials yields [Fn+1−2k(x) − Fn−1−2k(x)] Fn+1−2k(x) ⌊n/2⌋ n n
xn+1 = xFn(x) + (−1)k − xFn−2k(x) k=1 = Fn+1(x) − Fn−1(x) + (−1)k − k=1 = Fn+1(x) − Fn−1(x) + (−1)k − k=1 ⌊n/2⌋ = Fn+1(x) + (−1)k k=1 n n
− Fn+1−2k(x) k k−1 ⌊n/2⌋ n n
k k−1 ⌊n/2⌋ n n
− Fn−1(x) + (−1)k−1 k=2 − Fn+1−2k(x) k−1 k−2 Fn+1−2k (x). − (−1)k−1 − k k−1 ⌊n/2⌋ n n
− (−1)k − Fn−1−2k(x). k k−1 Our end goal is to combine these two summations into one. To accomplish this, note that shifting the indeces of the second summation up by 1 and moving the Fn−1(x) gives ⌊n/2⌋ n n
xn+1 = Fn+1(x) + (−1)k − Fn+1−2k(x) k=1 k k−1 k=1 ⌊n/2⌋+1 n n k k−1 ⌊n/2⌋+1 n n
k=1 k−1 k−2 Now we are able to combine the summations together. First, we deal with the case where n + 1 − 2k ̸= 0. Note that in this case, it is not hard to see that the coefficient of Fn+1−2k(x) is k n n k−1 n n (−1) k − k−1 −(−1) k−1 − k−2 k n n n n =(−1) k − k−1 + k−1 − k−2 k n n n n =(−1) k + k−1 − k−1 + k−2 k n+1 n+1 =(−1) k−k−1. The case where n + 1 − 2k = 0 (i.e. k = n+1 ) is a bit trickier. Note that the only summation that 2 contains an F0(x) term is the second one. Thus, we may conclude that the coefficient of F0(x) in the final expansion is (n+1)/2 n n (−1) (n−1)/2 − (n−3)/2 . In order for our hypothesis to be correct, it suffices to show that this equals (n+1)/2 n+1 n+1 (n+1)/2 − (n−1)/2 . (−1) Toprovethis,weneedtobeslightlyclever: since n+1 +n−1 =n,wehave n = n (n−1)/2 (n+1)/2 this point, we can apply the same logic as we did above to reach the desired conclusion. 2 2 . After We have thus shown in this case that ⌊(n+1)/2⌋ n + 1 n + 1
xn+1 = Fn+1(x) + (−1)k − k=1 Fn+1−2k(x), which is what we wanted. CASE 2: n is even. This case is actually very similar to the previous case, so we won’t show work here; the only difference relates to that edge case we described above. More specifically, note that we can’t say xFn−2k(x) = Fn+1−2k(x) − Fn−1−2k(x) for k = n/2, since then the second term is F−1(x), which is bad. Instead, we write xF0(x) = F1(x). Details are left to the reader. We have thus proven the hypothesis true for n + 1, and so by the Principle of Mathematical Induction we are done. Now we work on maximizing the λk. Note that from the above work we may extract the λk terms to get n n
|λn−2k|= k − k−1 for all 0 ≤ k ≤ 500. There are many different ways to maximize this expression; the following is only one of those ways. Note that n n |λn−2(k+1)| k + 1 − k |λn−2k| = n n
k k−1 k−k−1 n! −n! = (n−k−1)!(k+1)! (n−k)!k! n!− n! (n − k)!k! (n − k + 1)!(k − 1)! = (n−k+1)(n−k)−(n−k+1)(k+1) (n − k + 1)(k + 1) − (k + 1)k = (n−k+1)(n−2k−1). (k + 1)(n − 2k + 1) Setting this ratio to be less than 1 and expanding yields (n−k+1)(n−2k−1)<(k+1)(n−2k+1) =⇒ 4k2 −4kn+(n2 −n−2)<0. Note that by the Quadratic Formula the solutions to 4k2 − 4kn + (n2 − n − 2) = 0 are k = 4n± (4n)2 −4(4)(n2 −n−2) = n±√n+2. 2·4 2 The positive root gives a value of k which is above our range, so the largest value of k for which |λn−2(k+1)| < √ |λn−2k| is k = ⌊n− n+2⌋. For n = 1000, this gives k = 484, and so |λn−2k| = |λ32| is the maximum over all 2 λi. The requested answer is thus 32. I am too lazy to latex this.