A recurrence for the sequence {F_{F_{n}}, n ≥ 0} Chris Street, http://www.codehappy.net/

1 Definitions.

The Fibonacci sequence we all love is defined by

F_{0} = 0, F_{1} = 1, F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2.  (1)

This paper will address some interesting properties of the sequence

F_{n}^{(2)} = F_{F_{n}}, n ≥ 0  (2)

which begins {0, 1, 1, 1, 2, 5, 21, 233, 10946, 5702887, 139583862445...}.

Theorem 1.

\frac{F_{n+3}^{(2)}}{F_{n+2}^{(2)}} ∼ \frac{F_{n+2}^{(2)}}{F_{n}^{(2)}} , or F_{n+3}^{(2)}F_{n}^{(2)} ∼ F_{n+2}^{(2)}^{2}.  (3)

Proof. Recall Binet’s formula

F_{n} = \frac{ϕ^{n} − ψ^{n}}{\sqrt{5}} , where ϕ = \frac{1 + \sqrt{5}}{2}, ψ = \frac{1 − \sqrt{5}}{2}.  (4)

This gives

F_{n+3}^{(2)}F_{n}^{(2)} = \frac{(ϕ^{F_{n+3}} − ψ^{F_{n+3}})(ϕ^{F_{n}} − ψ^{F_{n}})}{5}

= \frac{(ϕ^{F_{n+3}+F_{n}} + ψ^{F_{n+3}+F_{n}}) − ϕ^{F_{n+3}}ψ^{F_{n}} − ϕ^{F_{n}}ψ^{F_{n+3}}}{5}

= \frac{(ϕ^{F_{n+3}+F_{n}} + ψ^{F_{n+3}+F_{n}}) − (ϕψ)^{F_{n}}(ϕ^{F_{n+3}−F_{n}} + ψ^{F_{n+3}−F_{n}})}{5}

= \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − (ϕψ)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{5}

Since ϕψ = −1, we have

F_{n+3}^{(2)}F_{n}^{(2)} = \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − (−1)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{5}  (5)

Also,

\begin{aligned}F_{n+2}^{(2)}^{2} & = \frac{(ϕ^{F_{n+2}} − ψ^{F_{n+2}})(ϕ^{F_{n+2}} − ψ^{F_{n+2}})}{5} \\ & = \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − 2ψ^{F_{n+2}}ϕ^{F_{n+2}}}{5} \\ & = \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − 2(−1)^{F_{n+2}}}{5} \end{aligned}  (6)

We seek to prove

lim_{n→∞} \frac{F_{n+3}^{(2)}F_{n}^{(2)}}{F_{n+2}^{(2)}^{2}} = 1

lim_{n→∞} \frac{F_{n+3}^{(2)}F_{n}^{(2)}}{F_{n+2}^{(2)}^{2}} = lim_{n→∞} \frac{\frac{(ϕ^{2F_{n+2}} +ψ^{2F_{n+2}} )−(−1)^{Fn} (ϕ^{2F_{n+1}} +ψ^{2F_{n+1}} )}{5}}{\frac{(ϕ^{2F_{n+2}} +ψ^{2F_{n+2}} )−2(−1)^{F_{n+2}}}{5}}

= lim_{n→∞} \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − (−1)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − 2(−1)^{F_{n+2}}}

As n gets large, 2 ≪ (ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}), so the 2(−1)^{F_{n+2}} term may be ignored:

\begin{matrix}lim_{n→∞} & \frac{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}}) − (−1)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}})} \\ = & lim_{n→∞} 1 − \frac{(−1)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}})} \end{matrix}

I will pause to make a note. Notice that if F_{n} ≡ 1 (mod 2), or equivalently, n ≢ 0 (mod 3), the quantity on the inside of the limit is a bit greater than 1; otherwise, it is a bit smaller.

Now what we want is to show that

lim_{n→∞} \frac{(−1)^{F_{n}}(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}})} = 0

We may take the absolute value inside the limit to rid ourselves of the (−1)^{F_{n}} term. So it is sufficient to show that

lim_{n→∞} \frac{(ϕ^{2F_{n+1}} + ψ^{2F_{n+1}})}{(ϕ^{2F_{n+2}} + ψ^{2F_{n+2}})} = 0

As n → ∞, ψ^{n} → 0, so we are left with the easy task of showing

lim_{n→∞} \frac{ϕ^{2F_{n+1}}}{ϕ^{2F_{n+2}}} = 0

\frac{ϕ^{2F_{n+1}}}{ϕ^{2F_{n+2}}} = ϕ^{2(F_{n+1}−F_{n+2})} = ϕ^{−2F_{n}} → 0, so our work is done. ■

This sequence converges very quickly. Indeed, \frac{F_{12}^{(2)}F_{9}^{(2)}}{F_{11}^{(2)}^{2}} ≈ 1 − (10^{−14}).

Theorem 2. A recurrence for F_{n}^{(2)}.

F_{n}^{(2)} = \frac{F_{n−1}^{(2)}^{2} − (−1)^{F_{n−3}}F_{n−4}^{(2)}F_{n−1}^{(2)} − (−1)^{F_{n−2}}F_{n−3}^{(2)}^{2}}{F_{n−3}^{(2)}} , n ≥ 4.

Proof. We rewrite the right side using Binet’s formula:

\frac{(ϕ^{F_{n−1}} − ψ^{F_{n−1}})^{2} − (−1)^{F_{n−3}}(ϕ^{F_{n−4}} − ψ^{F_{n−4}})(ϕ^{F_{n−1}} − ψ^{F_{n−1}}) − (−1)^{F_{n−2}}(ϕ^{F_{n−3}} − ψ^{F_{n−3}})^{2}}{\sqrt{5}(ϕ^{F_{n−3}} − ψ^{F_{n−3}})} ; =\frac{(ϕ^{F_{n−1}} − ψ^{F_{n−1}})^{2} − (ϕψ)^{F_{n−3}}(ϕ^{F_{n−4}} − ψ^{F_{n−4}})(ϕ^{F_{n−1}} − ψ^{F_{n−1}}) − (ϕψ)^{F_{n−2}}(ϕ^{F_{n−3}} − ψ^{F_{n−3}})^{2}}{\sqrt{5}(ϕ^{F_{n−3}} − ψ^{F_{n−3}})}

Now, we will simplify the numerator:

(ϕ^{F_{n−1}}−ψ^{F_{n−1}})^{2}−(ϕψ)^{F_{n−3}}(ϕ^{F_{n−4}}−ψ^{F_{n−4}})(ϕ^{F_{n−1}}−ψ^{F_{n−1}})−(ϕψ)^{F_{n−2}}(ϕ^{F_{n−3}}−ψ^{F_{n−3}})^{2} = ϕ^{2F_{n−1}}−ϕ^{F_{n−4}+F_{n−3}+F_{n−1}}ψ^{F_{n−3}}+ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−4}+F_{n−3}}−ϕ^{2F_{n−3}+F_{n−2}}ψ^{F_{n−2}}+

2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}} − ϕ^{F_{n−2}}ψ^{2F_{n−3}+F_{n−2}} − 2ϕ^{F_{n−1}}ψ^{F_{n−1}} + ψ^{2F_{n−1}}+

ϕ^{F_{n−4}+F_{n−3}}ψ^{F_{n−3}+F_{n−1}} − ϕ^{F_{n−3}}ψ^{F_{n−4}+F_{n−3}+F_{n−1}}

Using F_{n−4} + F_{n−3} + F_{n−1} = F_{n}, we may write:

ϕ^{2F_{n−1}}−ϕ^{F_{n}}ψ^{F_{n−3}}+ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−4}+F_{n−3}}−ϕ^{2F_{n−3}+F_{n−2}}ψ^{F_{n−2}}+2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}}− ϕ^{F_{n−2}}ψ^{2F_{n−3}+F_{n−2}}−2ϕ^{F_{n−1}}ψ^{F_{n−1}}+ψ^{2F_{n−1}}+ϕ^{F_{n−4}+F_{n−3}}ψ^{F_{n−3}+F_{n−1}}−ϕ^{F_{n−3}}ψ^{F_{n}} Since 2F_{n−1} = F_{n} + F_{n−3}, this is equal to

ϕ^{F_{n}+F_{n−3}}−ϕ^{F_{n}}ψ^{F_{n−3}}+ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−4}+F_{n−3}}−ϕ^{2F_{n−3}+F_{n−2}}ψ^{F_{n−2}}+2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}}− ϕ^{F_{n−2}}ψ^{2F_{n−3}+F_{n−2}}−2ϕ^{F_{n−1}}ψ^{F_{n−1}}+ψ^{F_{n}+F_{n−3}}+ϕ^{F_{n−4}+F_{n−3}}ψ^{F_{n−3}+F_{n−1}}−ϕ^{F_{n−3}}ψ^{F_{n}} Now we use F_{n−4} + F_{n−3} = F_{n−2} :

ϕ^{F_{n}+F_{n−3}}−ϕ^{F_{n}}ψ^{F_{n−3}}+ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−2}}−ϕ^{2F_{n−3}+F_{n−2}}ψ^{F_{n−2}}+2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}}− ϕ^{F_{n−2}}ψ^{2F_{n−3}+F_{n−2}} −2ϕ^{F_{n−1}}ψ^{F_{n−1}} +ψ^{F_{n}+F_{n−3}} +ϕ^{F_{n−2}}ψ^{F_{n−3}+F_{n−1}} −ϕ^{F_{n−3}}ψ^{F_{n}} Since 2F_{n−3} + F_{n−2} = F_{n−3} + F_{n−1} :

ϕ^{F_{n}+F_{n−3}}−ϕ^{F_{n}}ψ^{F_{n−3}}+ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−2}}−ϕ^{F_{n−3}+F_{n−1}}ψ^{F_{n−2}}+2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}}− ϕ^{F_{n−2}}ψ^{F_{n−3}+F_{n−1}} − 2ϕ^{F_{n−1}}ψ^{F_{n−1}} + ψ^{F_{n}+F_{n−3}} + ϕ^{F_{n−2}}ψ^{F_{n−3}+F_{n−1}} − ϕ^{F_{n−3}}ψ^{F_{n}}

= ϕ^{F_{n}+F_{n−3}} − ϕ^{F_{n}}ψ^{F_{n−3}} + 2ϕ^{F_{n−3}+F_{n−2}}ψ^{F_{n−3}+F_{n−2}} − 2ϕ^{F_{n−1}}ψ^{F_{n−1}}+

ψ^{F_{n}+F_{n−3}} − ϕ^{F_{n−3}}ψ^{F_{n}}

Finally we use F_{n−3} + F_{n−2} = F_{n−1}:

ϕ^{F_{n}+F_{n−3}} − ϕ^{F_{n}}ψ^{F_{n−3}} + 2ϕ^{F_{n−1}}ψ^{F_{n−1}} − 2ϕ^{F_{n−1}}ψ^{F_{n−1}} + ψ^{F_{n}+F_{n−3}} − ϕ^{F_{n−3}}ψ^{F_{n}}

= ϕ^{F_{n}+F_{n−3}} − ϕ^{F_{n}}ψ^{F_{n−3}} + ψ^{F_{n}+F_{n−3}} + −ϕ^{F_{n−3}}ψ^{F_{n}}

= (ϕ^{F_{n−3}} − ψ^{F_{n−3}})(ϕ^{F_{n}} − ψ^{F_{n}})

With the numerator simplified, the right side of the equation becomes

\frac{(ϕ^{F_{n−3}} − ψ^{F_{n−3}})(ϕ^{F_{n}} − ψ^{F_{n}})}{(ϕ^{F_{n−3}} − ψ^{F_{n−3}})\sqrt{5}} = \frac{(ϕ^{F_{n}} − ψ^{F_{n}})}{\sqrt{5}} = F_{F_{n}}.■