Zeckendorf Representation of Integer shifted Left

From ProofWiki
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

Retrieved from "https://proofwiki.org/w/index.php?title=Zeckendorf_Representation_of_Integer_shifted_Left&oldid=590116"