The following is from Clark Kimberling’s problems page.

Accepted solution

f(n) is never 3

Remark
Note that f(n) = floor(g(n)) where g(n) = n × frac(nG)   [frac() = fractional part].

Hence G can be replaced by frac(G), and this is done below.

If we look at the values of g(n) we find empirically that they have a sequence of discrete accumulation points, thus:

g(n) tends from above to 0.477 =? 1/5^1/2 for n = 1, 2, 5, 13, …
g(n) tends from above to 1.789 =? 4/5^1/2 for n = 4, 10, 26, 68, …
g(n) tends from above to 2.236 =? 5/5^1/2 for n = 3, 7, 18, 47, …
g(n) tends from above to 4.025 =? 9/5^1/2 for n = 6, 15, 39, 102, …
g(n) tends from above to 4.919 =? 11/5^1/2 for n = 9, 12, 23, 31, …

Since g(1), g(4) and g(3) are all less than 3 the result follows. So we need to prove this empirical finding.

Proof
Let a = (5^1/2 + 1)/2,  b = (5^1/2 – 1)/2 = frac(G).    Note that ab = 1.

The n^th Fibonacci number F_n = 5^–1/2[aⁿ – (–b)ⁿ]    (in the notation F₀ = 0, F₁ = F₂ = 1, …)

and a bit of calculation shows that frac(F_2m+1b) = F_2m+1b – F_2m = b^2m+1.

Lemma Every positive integer n can be expressed as a combination of distinct odd-indexed Fibonacci numbers:

n = F_2p+1 ± F_2q+1 ± … + F_2z+1

where each coefficient is ±1 and the largest and smallest terms both have coefficient +1.

Proof of lemma, by induction

1 = F₁
2 = F₃
3 = F₃ + F₁
4 = F₅ – F₃ + F₁
5 = F₅
6 = F₅ + F₁
7 = F₅ + F₃
8 = F₅ + F₃ + F₁

Having got F_2m = F_2m–1 + F_2m–3 + … + F₁, continue to F_2m+1 by expressing F_2m = F_2m+1 – F_2m–1 and using the previous results. The term F_2m–1 may cancel:

9 = F₇ – F₅ + F₁
10 = F₇ – F₅ + F₃
11 = F₇ – F₅ + F₃ + F₁
12 = F₇ [– F₅ + F₅] – F₃ + F₁
13 = F₇ [– F₅ + F₅]

Now continue to F_2m+2 with leading term F_2m+1 plus the previous results:

14 = F₇ + F₁
…
21 = F₇ + F₅ + F₃ + F₁

(The representation is not always unique; see “By the way” near the end of this solution.)

End of lemma.

To get frac(nb), express n as in the lemma and use frac(F_2m+1b) = b^2m+1. We just add the terms ±b^2m+1. This works because

b + b³ + b⁵ + b⁷ + … = 1

so that (i) sum < 1 (ii) sum >= 0, because the coefficient of the largest term (smallest power of b) is +1.

Next look at g(n) = n × frac(nb). For simplicity, this will be done by means of a typical example, in which

n = F_2m+7 – F_2m+3 + F_2m+1 (m = 0, 1, 2, …)

corresponding to n = 12, 31, … . We have (using ab = 1)

g(n) = 5^–1/2(a^2m+7 + b^2m+7 – a^2m+3 – b^2m+3 + a^2m+1 + b^2m+1)(b^2m+7 – b^2m+3 + b^2m+1)

= 5^–1/2[3 + (a⁶ + b⁶) – (a⁴ + b⁴) – (a² + b²) + (b^2m+7 – b^2m+3 + b^2m+1)²]

For k = 1, 2, 3, … let E_k = a^2k + b^2k = F_2k–1 + F_2k+1. Thus

E₁ = 3, E₂ = 7, E₃ = 18, E₄ = 47, … . Then

g(n) = 5^–1/2(3 + E₃ – E₂ – E₁ + R) = 5^–1/2(11 + R),

where 0 < R < 1 and R tends to 0 as m tends to infinity. This confirms part of the empirical finding above.

Note that the constant 11 is obtained as (1 – a² + a⁶)(1 – b² + b⁶). Since ab = 1 we also have 11 = (1 – a⁴ + a⁶)(1 – b⁴ + b⁶) corresponding to n = F_2m+7 – F_2m+5 + F_2m+1 = 9, 23, …. The accumulation point 11/5^1/2 (unlike the smaller ones) is the limit of two interleaved series.

Let the accumulation points be L/5^1/2 where empirically we’ve noticed L = 1, 4, 5, 9, 11. In general the L values are:

(1)(1) = 1
(1 + a²)(1 + b²) = 5
(1 – a² + a⁴)(1 – b² + b⁴) = 4
(1 + a⁴)(1 + b⁴) = 9
(1 – a² + a⁶)(1 – b² + b⁶) = 11
(1 – a⁴ + a⁶)(1 – b⁴ + b⁶) = 11
and so on for all similar combinations of even powers, in which the coefficient of the highest power used is +1.

If the highest power used is 2k (k = 1, 2, 3…) then the lowest possible L value is

(1 – a² – a⁴ … – a^2k–2 + a^2k) (1 – b² – b⁴ … – b^2k–2 + b^2k)

which after a bit of calculation is found to be

F_2k–3 + F_2k–5 + 2 (with the natural definitions F_–1 = 1, F_–3 = 2).

For k = 1, 2, 3, 4, 5, … this gives L = 5, 4, 5, 9, 40, … with the values increasing after L = 4. (By the way, L = 5 is repeated because F_2m+7 – F_2m+5 – F_2m+3 + F_2m+1 = F_2m+5 + F_2m+3.)

So the empirical list at the start includes all L values <= 9. This proves that either g(n) <= g(3) = 2.562 or g(n) > 9/5^1/2 = 4.025, and hence that f(n) = floor(g(n)) is never 3, QED.