## You are here

Homeproof that every positive integer has a Zeckendorf representation

## Primary tabs

# proof that every positive integer has a Zeckendorf representation

Theorem. Every positive integer $n$ has a Zeckendorf representation as a sum of non-consecutive Fibonacci numbers $F_{i}$.

If an integer $n=F_{k}$, where $F_{x}$ refers to a Fibonacci number, then $Z_{k}=1$ and $Z_{i}=0$ for all $0<i<k$, where $Z$ is an array of binary digits and $k$ is the index of the most significant digit.

Otherwise, we assign $j=n-F_{i}$ where $F_{i}$ is the largest Fibonacci number such that $F_{i}<n$. Then $Z_{i}>0$. It is obvious that $j<F_{i}$, because it can be safely assumed at this juncture that $F_{{i-2}}$ and $F_{{i-1}}$ are distinct, that $F_{{i-2}}<F_{{i-1}}$ and therefore $F_{i}<2F_{{i-1}}$. This proves that $Z_{i}$ must be 1, but no more than that. If $j$ is a Fibonacci number, we can stop now, otherwise, we must again subtract the largest possible Fibonacci number, decrement $i$ accordingly and set the appropriate $Z_{i}=1$. The farthest this iterative process can go is to $i=1$, corresponding to $F_{1}=1$.

Furthermore, the 1s in $Z$ must have 0s in between them because any two consecutive 1s, such as at, say, $Z_{i}$ and $Z_{{i-1}}$ would indicate a failure to recognize that $F_{{i-1}}+F_{i}=F_{{i+1}}$, and thus $Z_{i}$ and $Z_{{i-1}}$ can be set to zero in favor of setting $Z_{{i+1}}$ to 1. (As a side note, no binary representation of a Mersenne number should be mistaken for a Zeckendorf representation; in other words, there are no repunits in Zeckendorf representations).

## Mathematics Subject Classification

11A63*no label found*11B39

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections