Zeckendorf Representation of Integer shifted Left
Jump to navigation
Jump to search
Theorem
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = \floor {x + \phi^{-1} }$
where:
- $\floor {\, \cdot \,}$ denotes the floor function
- $\phi$ denotes the golden mean.
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $n$ be expressed in Zeckendorf representation:
- $n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$
with the appropriate restrictions on $k_1, k_2, \ldots, k_r$.
Then:
- $F_{k_1 + 1} + F_{k_2 + 1} + \cdots + F_{k_r + 1} = \map f {\phi n}$
Proof
We have:
\(\ds F_{k_j + 1} \hat \phi + F_{k_j}\) | \(=\) | \(\ds \hat \phi^{k_j + 1}\) | Fibonacci Number by One Minus Golden Mean plus Fibonacci Number of Index One Less | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds F_{k_j + 1}\) | \(=\) | \(\ds \hat \phi^{k_j} - \frac {F_{k_j} } {\hat \phi}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \hat \phi^{k_j} + \phi F_{k_j}\) | Reciprocal Form of One Minus Golden Mean |
Hence:
\(\ds F_{k_1 + 1} + F_{k_2 + 1} + \cdots + F_{k_r + 1}\) | \(=\) | \(\ds \phi \paren {F_{k_1} + F_{k_2} + \cdots + F_{k_r} } + \paren {\hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \phi n + \paren {\hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} }\) |
We have that:
- $\hat \phi^3 + \hat \phi^5 + \hat \phi^7 + \cdots \le \hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} \le \hat \phi^2 + \hat \phi^4 + \hat \phi^6 + \cdots$
Then:
\(\ds \hat \phi^3 + \hat \phi^5 + \hat \phi^7 + \cdots\) | \(=\) | \(\ds \hat \phi^3 \paren {1 + \hat \phi^2 + \hat \phi^4 + \cdots}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\hat \phi^3} {1 - \hat \phi^2}\) | Sum of Infinite Geometric Sequence | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\phi^2 \hat \phi^3} {\phi^2 - \phi^2 \hat \phi^2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {-1}^2 \hat \phi} {\phi^2 - \paren {-1}^2}\) | Golden Mean by One Minus Golden Mean equals Minus 1 | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\hat \phi} {\phi^2 - 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {1 - \phi} {\phi^2 - 1}\) | Definition of One Minus Golden Mean | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {1 - \phi} {1 + \phi - 1}\) | Square of Golden Mean equals One plus Golden Mean | |||||||||||
\(\ds \) | \(=\) | \(\ds \phi^{-1} - 1\) |
Then:
\(\ds \hat \phi^2 + \hat \phi^4 + \hat \phi^6 + \cdots\) | \(=\) | \(\ds \frac 1 {\hat \phi} \paren {\hat \phi^3 + \hat \phi^5 + \hat \phi^7 + \cdots}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {\hat \phi} \paren {\phi^{-1} - 1}\) | from above | |||||||||||
\(\ds \) | \(=\) | \(\ds -\phi \paren {\frac 1 \phi - 1}\) | Reciprocal Form of One Minus Golden Mean | |||||||||||
\(\ds \) | \(=\) | \(\ds -1 + \phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {\phi}\) | Definition 3 of Golden Mean | |||||||||||
\(\ds \) | \(=\) | \(\ds \phi^{-1}\) |
Thus:
- $\phi^{-1} - 1 \le \hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} \le \phi^{-1}$
and the result follows.
$\blacksquare$
Historical Note
According to Donald E. Knuth in his The Art of Computer Programming: Volume 1: Fundamental Algorithms, 3rd ed. of $1997$, this result was demonstrated by Yuri Vladimirovich Matiyasevich in $1990$, but no further details are given.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $41$