TAOCP 1.2.8 Exercise 31

Exercise 31. [M20] Show that $F_{2n}\phi \bmod 1 = 1-\phi^{-2n}$ and $F_{2n+1}\phi \bmod 1 = \phi^{-2n-1}$.

Verified: no
Solve time: -

Solution

We are asked to compute $F_n \phi \bmod 1$, that is, the fractional part of $F_n \phi$. By definition, for any real number $x$, $x \bmod 1 = x - \lfloor x \rfloor$.

From equation (14) in Section 1.2.8, we have the Binet formula

$$ F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, \qquad \hat{\phi} = 1-\phi = \frac{1-\sqrt{5}}{2}. $$

Multiplying both sides by $\phi$ gives

\begin{align*}

F_n \phi &= \frac{\phi^{n+1} - \hat{\phi}^n \phi}{\sqrt{5}} \

&= \frac{\phi^{n+1} - (\hat{\phi})^n \phi}{\sqrt{5}}.

\end{align*}

Recall the identity $\phi^2 = \phi + 1$, so $\phi^{n+1} = \phi^2 \phi^{,n-1} = (\phi+1)\phi^{,n-1}$. We will exploit a simpler approach by observing the fractional part of $F_n \phi$ comes entirely from the term involving $\hat{\phi}$, because

$$ \frac{\phi^{n+1}}{\sqrt{5}} = F_{n+1} + \frac{\hat{\phi}^{,n+1}}{\sqrt{5}}. $$

Indeed, using equation (14) for $F_{n+1}$,

$$ F_{n+1} = \frac{\phi^{,n+1} - \hat{\phi}^{,n+1}}{\sqrt{5}} \implies \frac{\phi^{,n+1}}{\sqrt{5}} = F_{n+1} + \frac{\hat{\phi}^{,n+1}}{\sqrt{5}}. $$

Hence,

\begin{align*}

F_n \phi &= \frac{\phi^{,n+1} - \phi \hat{\phi}^n}{\sqrt{5}} \

&= F_{n+1} + \frac{\hat{\phi}^{,n+1}}{\sqrt{5}} - \frac{\phi \hat{\phi}^n}{\sqrt{5}} \

&= F_{n+1} + \frac{\hat{\phi}^n(\hat{\phi} - \phi)}{\sqrt{5}}.

\end{align*}

Since $\hat{\phi} - \phi = (1-\phi) - \phi = 1 - 2\phi = -\sqrt{5}$, we obtain

$$ F_n \phi = F_{n+1} - \frac{\hat{\phi}^n \sqrt{5}}{\sqrt{5}} = F_{n+1} - \hat{\phi}^n. $$

Thus the fractional part is

$$ F_n \phi \bmod 1 = 1 - \hat{\phi}^n, \qquad \text{because } F_{n+1} \text{ is an integer}. $$

We now evaluate separately for even and odd indices:

Even index: Let $n \mapsto 2n$. Then

$$ F_{2n} \phi \bmod 1 = 1 - \hat{\phi}^{2n}. $$

Since $\hat{\phi} = 1 - \phi$, we have

$$ \hat{\phi}^{2n} = (1-\phi)^{2n} = (-\phi^{-1})^{2n} = \phi^{-2n}. $$

Hence

$$ F_{2n} \phi \bmod 1 = 1 - \phi^{-2n}. $$

Odd index: Let $n \mapsto 2n+1$. Then

$$ F_{2n+1} \phi \bmod 1 = 1 - \hat{\phi}^{2n+1}. $$

Similarly, $\hat{\phi}^{2n+1} = (1-\phi)^{2n+1} = (-\phi^{-1})^{2n+1} = -\phi^{-2n-1}$, so

$$ F_{2n+1} \phi \bmod 1 = 1 - (-\phi^{-2n-1}) = \phi^{-2n-1}. $$

This completes the derivation.

$$ \boxed{ F_{2n} \phi \bmod 1 = 1 - \phi^{-2n}, \qquad F_{2n+1} \phi \bmod 1 = \phi^{-2n-1} } $$