Zeckendorf Representation of Integer shifted Right
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^{-1} n}$
Proof
Follows directly from Zeckendorf Representation of Integer shifted Left, substituting $F_{k_j - 1}$ for $F_{k_j}$ throughout.
$\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$