# Zeckendorf Representation of Integer shifted Left

## Theorem

Let $\map f x$ 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.