# Two Non-Negative Integers have Zeckendorf Representations of which one is Shifted Representation of the Other

Jump to navigation
Jump to search

## Theorem

Let $m, n \in \Z_{\ge 0}$ be non-negative integers.

Then there exists a unique set of integers:

- $\left\{ {k_1, k_2, \ldots, k_r}\right\}$

where:

- $k_1 \gg k_2 \gg \cdots \gg k_r$

where $a \gg b$ denotes that $a - b > 1$

such that:

- $m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$

and:

- $n = F_{k_1 + 1} + F_{k_2 + 1} + \cdots + F_{k_r + 1}$

Note that:

- each of the $k$'s may be negative

and:

- $r$ may equal $0$.

## Proof

## Sources

- 1968: David A. Klarner:
*Partitions of N into Distinct Fibonacci Numbers*(*The Fibonacci Quarterly***Vol. 6**: 235 – 244)

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $42$