POLYA016: Iteration of sums of Fibonacci divisors  (proposed by Antreas P. Hatzipolakis, 11/30/01).

Let (F_n) be the sequence of Fibonacci numbers: F_1 = 1, F_2 = 1, and F_(k+1) = F_k + F_(k-1) for k \ge 3. For every positive integer n, define

g(n) = 2 + sum(F_k, k \ge 3, F_k divides n but F_(k+1) does not divide n).

Show that the sequence  g(n), g(g(n)), g(g(g(n))), ... , is eventually constant.

Discussion. [SCL: 12/1/01]: One can easily verify that the sequence g(n), g(g(n)), ..., ends in 4 for small n, say 1<=n<=10.
 For larger n, if n is not a fibonacci number, then the largest F_k which divides n is at most n/2. The next F_j which contributes to the sum is at most F_{k-2}, etc. Thus,  g(n) \le F_k+F_{k-2}+F_{k-4}+... which is approximately
F_k*(1+\tau^{-2}+\tau^{-4}+\tau^{-6}+...)
=F_k/(1-\tau^{-2})
=\tau^2*F_k/(\tau^2-1)
=\tau*F_k,
where \tau = (1+\sqrt(5))/2.
Thus, when n is not a fibonacci number, g(n) is at most n*\tau/2 or approximatelt (0.8)*n.
Now, when n is a fibonnaci number, g(n) could be as high as n*\tau. Since this is rather close to the next fibonacci number, we examine things a little closer.
If n=F_k for some k, then F_{k-1}, by definition is not part of the sum, but we need to see that F_{k-2} is also not part of the sum. However, if F_{k-2} is part of the sum, then F_{k-2}=gcd(F_k, F_{k-2}), and since F_{k-1}=F_k-F_{k-2}, we have F_{k-2} divides F_{k-1}. But, gcd(F_r,F_s)=F_{gcd(r,s)}, and we must have F_{k-2}=1. But, we are excluding the small cases. Thus, we can assume that F_{k-3} is the next largest fibonacci number that divides n, and thus that g(n) is at most F_k+F_{k-3}+F_{k-5}+... which is approximately
F_k*(1+\tau^{-3}+\tau^{-5}+\tau^{-7}+...)
=F_k*(1+\tau^{-3}/(1-\tau^{-2}))
=F_k*(1+\tau^{-1}/(\tau^2-1}))
=F_k*(1+\tau^{-2})
=F_k*(3-\tau)
<F_{k+1} (for k>2).
So g(g(F_k)) is at most F_k*(3-\tau)*\tau/2 wich is about 1.12*F_k. This estimate is still a little too large, since we would like to see that g(g(n)) < n for n a fibonacci number. If we could also forbid F_{k-3} dividing F_k, we would have
g(n) is at most F_k+F_{k-4}+F_{k-6}+... which is approximately
F_k*(1+\tau^{-4}+\tau^{-5}+\tau^{-7}+...)
=F_k*(1+\tau^{-4}/(1-\tau^{-2}))
=F_k*(1+\tau^{-2}/(\tau^2-1}))
=F_k*(1+\tau^{-3})
=F_k*(2\tau-2)
and our bound on g(g(F_k)) is F_k.
Obviously, we can enumerate the small cases and then have none of F_{k-1}, F_{k-2}, F_{k-3}, F_{k-4} dividing F_k. Then, g(g(n))<n. To make F_{k-4} not divide F_k, for example, we note that gcd(F_k,F_{k-4})=F_{gcd(k-4,k)} is at most 3. Thus, if F_{k-4}>3, F_{k-4} does not divide F_k. That is, if k>8, then F_[k-4} does not divide F_k. SO, for n>21, g(n)<n if n is not a fibonacci number, and g(g(n))<n if n is a fibonacci number. In either case, the sequence g(n),g(g(n)),g(g(g(n))), is forced to decrease in that sense, until it reaches a n umber in the set {1,2,...,21}. But then, simple calculation for these values shows that we always terminate the sequence at 4.
Again, I'm roughing out the proof, and somebody else should feel free to cross the t's and dot the i's.
 

Bibliography.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]