ON THE NUMBER OF SUMMANDS INZECKENDORF DECOMPOSITIONSMURAT KOLOĞLU, GENE S. KOPP, STEVEN J. MILLER, AND YINGHUI WANG
Abstract. Zeckendorf proved that every positive integer has a unique representation as asum of non-consecutive Fibonacci numbers. Once this has been shown, it’s natural to ask how
many summands are needed. Using a continued fraction approach, Lekkerkerker proved thatthe average number of such summands needed for integers
in [Fn , Fn+1 ) is n/(α2 + 1) + O(1),√1+ 5where Fn is the nth Fibonacci number and α = 2 is the golden mean. Surprisingly, no
one appears to have investigated the distribution of the number of summands; our main result
is that this converges to a Gaussian as n → ∞. Moreover, such a result holds not just for
the Fibonacci numbers but many other problems, such as linear recurrence relations with
non-negative integer coefficients (which is a generalization of base B expansions of numbers)
and far-difference representations.
In general, the proofs involve adopting a combinatorial viewpoint and analyzing the resulting generating functions through partial fraction expansions and differentiating identities.
The resulting arguments become quite technical. The purpose of this paper is to concentrateon the special and most interesting case of the Fibonacci numbers, where the obstructions
vanish and the proofs follow from some combinatorics and Stirling’s formula; see [13] for
proofs in the general case.

1. Introduction
Fibonacci numbers are one of the most well-known and studied sequences in mathematics,
as well as one of the most enjoyable to play with. There are books, journals and conferences
dedicated to all their wondrous properties. The purpose of this article is to review two niceresults, namely Zeckendorf’s and Lekkerkerker’s Theorems, and discuss generalizations andrelated questions. We provide complete proofs for the Fibonacci sequence and refer the reader
to [13] for proofs of the general cases.
Before stating our results, we first set some notation. We study the (shifted) Fibonaccisequence given by F1 = 1, F2 = 2, F3 = 3, F4 = 5 and in general Fn = Fn−1 + Fn−2 . Note
our sequence is offset from the standard Fibonacci sequence {Fn } by 1, with Fn = Fn+1 . The
nth term in the sequence is given by the (shifted) Binet’s formula
√
α
1−α
1+ 5
n
n
Fn = √ · α − √ · (1 − α) , α =
,
(1.1)
2
n
5
where α is the golden mean. We will see below why it is convenient to study the shiftedsequence. We refer to the elements {Fn } as (shifted) Fibonacci numbers.

The first, second and fourth named authors were partially supported by NSF Grants DMS0855257,
DMS0970067, Williams College and the MIT Mathematics Department, and the second named author waspartially supported by NSF grant DMS0850577.

116

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
Zeckendorf (see for instance [16]) proved that every positive integer can be written uniquely
as a sum of non-adjacent (shifted) Fibonacci numbers. The proof is a straightforward induction. Note, though, how important it is that our series begins with just a single 1; if we had
two 1’s then the decompositions of many numbers into non-adjacent summands would not be
unique.
In the 1950’s, Lekkerkerker [10] answered the following question, which is a natural outgrowth of Zeckendorf’s theorem: On average, how many summands are needed in the Zeckendorf decomposition? Lekkerkerker proved that for integers in [Fn , Fn+1 ) the average numberof summands, as n → ∞, is α2n+1 + O(1) ≈ .276n.
Of course, one can ask these questions for more general recurrence relations. Zeckendorf’s
result has been generalized to several recurrence relations (see the 1972 special volume on
representations in the Fibonacci Quarterly, especially [6, 7], as well as [11]). Burger [2] proved
the analogous result for the mean number of summands for a generalization of Fibonacci
numbers, Gn = Gn−1 + Gn−2 + · · · + Gn−L . There is, of course, another generalization, whichinterestingly does not seem to have been asked. Namely, how are the number of summands
distributed about the mean for integers in [Fn , Fn+1 ). This is a very natural question to ask.
Both the question and the answer are reminiscent of the Erdős-Kac Theorem [4], which statesthat as n → ∞ the number of distinct prime divisors of integers
on the order of size n tends√
to a Gaussian with mean log log n and standard deviation log log n. (In [13], a companion
paper to this work, we show a connection between our result and the Erdős-Kac Theorem forrecurrence relations of depth 1.)
Our main result is that a similar statement about Gaussian behavior holds, not just for theshifted Fibonacci numbers, but for the large class of recurrence relations (which includes the
Fibonacci numbers as a special case) defined below.
Definition 1.1. We say a sequence {Hn }∞n=1 of positive integers is a Positive Linear Recurrence Sequence (PLRS) if the following properties hold:(1) Recurrence relation: There are non-negative integers L, c1 , . . . , cL such that
Hn+1 = c1 Hn + · · · + cL Hn+1−L ,with L, c1 and cL positive.
(2) Initial conditions: H1 = 1, and for 1 ≤ n < L we have

Hn+1 = c1 Hn + c2 Hn−1 + · · · + cn H1 + 1.
Pm
We call a decomposition m
i=1 ai Hm+1−i of a positive integer N (and the sequence {ai }i=1 )legal if a1 > 0, the other ai ≥ 0, and one of the following two conditions hold:• We have m < L and ai = ci for 1 ≤ i ≤ m.
• There exists s ∈ {0, . . . , L} such thata1 = c1 ,a2 = c2 ,...,as−1 = cs−1

andas < cs ,

(1.2)

m−s−`
as+1 , . . . , as+` = 0 for some ` ≥ 0, and {bi }i=1(with bi = as+`+i ) is legal.
Pm
If i=1 ai Hm+1−i is a legal decomposition of N , we define the number of summands (of thisdecomposition of N ) to be a1 + · · · + am .

Informally, a legal decomposition is one where we cannot use the recurrence relation to
replace a linear combination of summands with another summand, and the coefficient of eachsummand is appropriately bounded. For example, if Hn+1 = 2Hn + 3Hn−1 + Hn−2 , thenH5 +2H4 +3H3 +H1 is legal, while H5 +2H4 +3H3 +H2 is not (we can replace 2H4 +3H3 +H2
MAY 2011

117

THE FIBONACCI QUARTERLY
with H5 ), nor is 7H5 + 2H2 (as the coefficient of H5 is too large). Note the shifted Fibonacci
numbers are just the special case of L = 2 and c1 = c2 = 1.
We adopt a probabilistic language to state our main results.
Definition 1.2 (Associated Probability Space to a Positive Linear Recurrence Sequence). Let{Hn } be a Positive Linear Recurrence Sequence. For each n, consider the discrete outcome
spaceΩn = {Hn , Hn + 1, Hn + 2, . . . , Hn+1 − 1}
(1.3)
with probability measureX1, a ⊂ Ωn ;
(1.4)
Pn (A) =H
n+1 − Hnω∈Aω∈Ωnin other words, each of the Hn+1 − Hn numbers is weighted equally. We define the randomvariable Kn by setting Kn (ω) equal to the number of summands of ω ∈ Ωn in its legal decomposition. It is also convenient to study Kn = Kn − 1; every integer in Ωn must have at least one
Hn as a summand; thus Kn is the number of non-forced summands in a legal decomposition.
Implicit in this definition is that each integer has a unique legal decomposition; we will
prove this fact, and thus Kn is well-defined. Our main result is the following theorem.
Theorem 1.3. If {Hn }∞n=1 is a Positive Linear
P Recurrence Sequence then every positive
integer may be written uniquely as a legal sum i ai Hi (see Definition 1.1). Let Kn be therandom variable of Definition 1.2. Then E[Kn ] and Var(Kn ) are of order n, and as n → ∞,Kn and Kn converge to a Gaussian.
Our result extends Zeckendorf’s and Lekkerkerker’s Theorems to a large class of recurrence
relations, and further implies that the distribution of summands converges to a Gaussian.
The proof has three main ingredients. The first is to adopt a combinatorial point of view.
Previous approaches to Lekkerkerker’s Theorem were number theoretic, involving continued
fractions. We instead view this as a combinatorial problem, namely how many ways can wechoose elements in a set subject to some restrictions on what may be taken. This approachgives us an explicit formula for the number of N in [Hn , Hn+1 ) that have a given number ofsummands. For each interval [Hn , Hn+1 ) (i.e., for each n) we may thus associate a probability
function pn on [Hn , Hn+1 ) where pn (k) is the probability of having exactly k+1 summands. As
remarked earlier, we choose to write the density this way as every integer in [Hn , Hn+1 ) musthave Hn in its decomposition, and thus it is more natural to study the number of additional,
non-forced summands needed. Note pn is the density of the random variable Kn . We thenuse generating functions and differentiating identities to obtain tractable formulas for thesesummand functions pn , and prove our claims about the mean and the variance. We conclude
by showing that as n → ∞ the centered and normalized moments of pn tend to the momentsof the standard normal; by Markov’s Method of Moments this yields the Gaussian behavior.
We can gain a lot of intuition as to why these results are true by looking at the special
case of L = 1 and c1 = B > 0. For these choices, our sequence is just Hn = B n−1 ; in otherwords, we are looking at the base B decomposition of integers. Zeckendorf’s Theorem is now
clearly true, as every number has a unique representation. Lekkerkerker and the Gaussian
behavior are now just consequences of the Central Limit Theorem. For example, consider adecomposition of an N ∈ [B n , B n+1 ):N = a1 B n + a2 B n−1 + · · · + an+1 B 0 .

118

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
We have a1 ∈ {1, . . . , B − 1} and all other ai ∈ {0, . . . , B − 1}. We are interested in the
behavior, for large n, of a1 + · · · + an+1 as we vary over N in [B n , B n+1 ). Note for large n
the contribution of a1 is immaterial, and the remaining ai ’s can be understood by considering
the sum of n independent, identically distributed p
uniform random variables on {0, . . . , B − 1}(which have mean B−1
andstandard
deviation(B 2 − 1)/12). Denoting these by Ai , by2
the Central Limit Theorem A2 + · · · + An+1 converges to a Gaussian with mean B−1
2 n andp
2
standard deviation n (B − 1)/12.
Our approach is quite general, and can handle a variety of related problems. We state justone more, which allows us to see some very interesting behavior.
Recently Alpert [1] showed that every positive integer can be written uniquely as a sum anddifference of the shifted Fibonacci numbers {Fn }∞n=1 such that every two terms of the same
sign differ in index by at least 4, and every two terms of opposite sign differ in index by atleast 3; we call this the far-difference representation. For example,
2011 = F17 − F14 + F8 + F3 and 1900 = F17 − F14 − F10 + F6 + F2 .
P
If Sn = 0<n−4i≤n Fn−4i = Fn + Fn−4 + · · · for positive n and 0 otherwise, then for eachN ∈ (Sn−1 , Sn ] the first term in its far-difference representation is Fn . Note that 0 has theempty representation. We can show the following (see [13] for the proof).
Theorem 1.4. Consider
space Ωn = {Sn−1 + 1, Sn−1 + 2, . . . , Sn } with probP the outcome
1ability measure P(A) = ω∈A Sn −SforA ⊂ Ωn . Let Kn and Ln be the random variables
n−1denoting the number of positive and negative shifted Fibonacci summands in the far-difference
representation (they are well-defined by [1]). As n → ∞, for any real numbers a and b the
random variable aKn + bLn converges to √a Gaussian. The expected value of Kn (whichis√371−113 5
15+21 5nα/2 more than that of Ln ) is 10 ++ o(1); the variance of both is of size 1000 n.
40
Kn and Ln are negatively correlated, with a correlation coefficient of −(21 − 2α)/(29 + 2α).
Further, Kn + Ln and Kn − Ln are independent random variables as n → ∞, which implies thetotal number of shifted Fibonacci numbers is independent of the excess of positive to negative
summands.
Unfortunately, our arguments become involved and technical to handle all of the casesin Theorems 1.3 and 1.4. In order to highlight the ideas without getting bogged down incomputations, in this note we concentrate on the most important special case of Theorem
1.3, namely the shifted Fibonacci numbers, and content ourselves with providing a sketch ofsome of the arguments in Theorem 1.4. We first describe our combinatorial perspective, whichyields

n−1−k

k
,
(1.5)
Fn−1
with pn (k) the probability that an N ∈ [Fn , Fn+1 ) has exactly k+1 summands in its Zeckendorf
decomposition. All of our theorems follow from knowing this density. The difficulties in thegeneral case are due to the fact that the corresponding formulas for the densities are far more
involved; here we can easily determine the behavior by applying Stirling’s formula.
We first use our explicit formula for pn (k) to prove Zeckendorf’s Theorem, and then sketch
how we can use it to prove Lekkerkerker’s Theorem for the mean µn , as well as computing thevariance σn2 . We then show that as n → ∞, pn (k) converges to a Gaussian with mean µn andvariance σn2 . While technically we could just immediately jump to the limiting behavior ofthe density, it would be very unmotivated not knowing the mean and the variance and either

pn (k) =MAY 2011

119THE FIBONACCI QUARTERLY
choosing the correct values by divine inspiration, or having them fall out of the resulting
algebra.
2. Combinatorial Perspective and Zeckendorf’s Theorem
The key input in our analysis is counting the number of solutions to a well-known Diophantine equation. This problem is also known as the stars and bars problem, the cookie problem,or the simplest case of Waring’s problem (see [12, 14]).
Lemma 2.1.
(1) The number of ways of dividing n identical objects among p distinct people is n+p−1
p−1 .
Equivalently, this is the number of solutions to y1 + · · · + yp = n with each yi a nonnegative integer.
(2) More generally, the number of solutions to y1 + · · · + yp = n with yi ≥ ci (each ci ap )+p−1
non-negative integer) is n−(c1 +···+c.
p−1

Proof. For (1): The two formulations are clearly equivalent; simply interpret yi as the numberof objects person i receives. To prove the claimed formula, imagine the m objects are in a row
and we add p − 1 items at the end. We now have n + p − 1 objects. There is a one-to-one
correspondence between assigning
the n objects to the p people and choosing p − 1 of n + p − 1objects. There are n+p−1
ways
tochoose p − 1 of the n + p − 1 items. All the items up to
p−1
the first one chosen go to person 1, then the items up to the second one chosen go to person
2, and so on.
For (2): We may write yi = xi + ci with each xi ≥ 0 a non-negative integer. Our problem
is equivalent to(x1 + c1 ) + · · · + (xp + cp ) = n,which becomes
x1 + · · · + xp = n − (c1 + · · · + cp ), xi ≥ 0,
whose solution is given by part (1).

There are two parts to Zeckendorf’s Theorem: not only does a decomposition exist of any
positive integer as a sum of non-consecutive Fibonacci numbers, but such a decomposition is
unique. As our combinatorial approach does require this uniqueness as an input, we provide
the standard proof below (or see, among others, [5, 16]).
Lemma 2.2 (Zeckendorf’s Theorem - Uniqueness of Decomposition). If two sums of nonconsecutive Fibonacci numbers are equal, then the two sums have the same summands.
Proof. Assume
Fn1 + Fn2 + · · · + Fnk = Fm1 + Fm2 + · · · + Fm`(2.1)
where n1 ≥ n2 ≥ · · · and m1 ≥ m2 ≥ · · · . Without loss of generality we may assume
Fn1 > Fm1 (as otherwise we would just remove some summands). As each decomposition isof non-adjacent summands, if we add 1 to the decomposition on the right of (2.1), the largest
it can be is Fm1 + Fm2 +1 , which itself is at most Fm1 +1 . For example, F6 + F4 + F2 + 1 =F6 + F4 + F3 = F6 + F5 = F7 . As Fn1 > Fm1 , we see that adding 1 to the right hand side of(2.1) yields a number at most Fn1 ; thus
contradiction.
120

Fn1 + Fn2 + · · · + Fnk > Fm1 + Fm2 + · · · + Fm` ,

(2.2)


VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
We are now in a position to prove the first part of Zeckendorf’s Theorem. In the course of
our proof we will derive (1.5), the claimed formula for pn (k).
Theorem 2.3 (Zeckendorf’s Theorem - Existence of Decomposition). Any natural number canbe expressed as a sum of non-consecutive shifted Fibonacci numbers. Further, the probabilityan
N ∈ [Fn , Fn+1 ) has exactly k + 1 summands in its Zeckendorf decomposition is n−1−k
/F
n−1
k
/F
(in other words, the density function of the random variable Kn is pn (k) = n−1−k
).
n−1
k

Proof. Consider all N in [Fn , Fn+1 ). The number of integers in this interval is Fn+1 − Fn =Fn−1 . We claim that each of these Fn−1 integers can be expressed as a sum of a certain subsetof {F1 , F2 , . . . , Fn } with the properties that no two consecutive Fibonacci numbers appear in
the sum and that Fn is one of the summands. From the arguments in the proof of Lemma
2.2, it is clear that Fn must appear in this sum since otherwise the sum would be too small
to be an element of [Fn , Fn+1 ).
We now translate the previous claim into the combinatorial formulation of Lemma 2.1.
Suppose we wish to have k summands in addition to the summand Fn in our sum, withno two summands adjacent. Clearly k ≤ b n−1
2 c. Choosing a valid set of k summands, say
Fm1 , . . . , Fmk , is equivalent to choosing k indices m1 , m2 , . . . , mk from the set {1, 2, . . . , n − 1},with the property that mi < m1+1 − 1 and n − 1 is not chosen (as otherwise we would havethe adjacent summands Fn−1 and Fn ).
We may assume k > 0, as there is only one way to choose no additional summands. We define
the auxiliary sequence yj as follows: y0 = m1 − 1, and for 1 ≤ j ≤ k, yj = mj+1 − mj − 1 (asnoted earlier, mk+1 = n). For example, with n = 9, k = 3, and the sequence F1 +F3 +F6 +F9 ,we have y0 = 0, y1 = 1, y2 = 2 and y3 = 2. Note y0 is the number of indices before the firstindex chosen, and for j > 0, yj equals the number of unused indices between mj and mj+1 .
Clearly we have y0 ≥ 0 and yj ≥ 1 for j > 0. Thus we have used k + 1 indices (including
the required index n associated with the largest summand, Fn ) and y0 + y1 + · · · + yk unused
indices from {1, 2, . . . , n}. Hence, we have(k + 1) + y0 + y1 + · · · + yk = n.

(2.3)

x0 + · · · + xk = n − 1 − 2k.

(2.4)

If we make the change of variables x0 = y0 and xj = yj − 1 for j > 0, then we have xj ≥ 0
for all j with no other constraints on these variables other than they must satisfy the identity
implicitly given by (2.3); that is
In other words, in view of Lemma 2.2 we have a bijection between the set of Zeckendorf
decompositions with k + 1 summands having Fn as its largest summand and the set of all
non-negative integer solutions to (2.4). By Lemma 2.1, the number of solutions to (2.4) isn−1−2k+(k+1−1)
n−1−k
=. Thus the number of Zeckendorf decompositions having largestkk+1−1
summand Fn is precisely
b n−1
c

2
X
n−1−k
,
(2.5)
k
k=0

which, by a well-known identity for binomial sums, equals Fn−1 (for a proof, see either [9]or Appendix A of [8]). As remarked, by Lemma 2.2, each one of these sequences gives rise
to a distinct Zeckendorf sum. Thus the number of Zeckendorf decompositions in the interval[Fn , Fn+1 ) is equal to Fn−1 , which is the total number of integers in that interval. As n wasarbitrary, and these intervals partition the set of natural numbers, we have shown that every
MAY 2011

121THE FIBONACCI QUARTERLY
natural number has a unique Zeckendorf decomposition, and the number of N in [Fn , Fn+1 )n−1−kwith exactly k + 1 summands in its decomposition is. In other words, the probabilitykof a number in this interval having precisely k + 1 summands is n−1−k/Fn−1 .
k
3. Lekkerkerker’s Theorem and the Variance

We sketch how our approach easily yields Lekkerkerker’s Theorem. We only provide a sketchas, of course, Lekkerkerker’s Theorem follows immediately from our proof of the Gaussian
behavior. We highlight the key steps as Lekkerkerker’s Theorem is of interest in its own right,
and it is nice to have a new, elementary proof of it (our proof of the Gaussian behavior will
involve Stirling’s formula, and is different than the arguments below).
The average number of summands needed in the Zeckendorf decomposition is just

b n−1
c
n−1−k
2
X
k
µn =
(k + 1)
Fn−1
k=0

= 1+

1

b n−1
c
2

Fn−1

k=0

E(n)
= 1+
.
Fn−1
Thus the problem is reduced to computing
b n−1
c
2

E(n) =

X
k=0

X

k



n−1−k
k


(3.1)




n−1−k
k
.
k

(3.2)

We can determine a closed-form expression for E(n) by first showing that it satisfies a certain
recurrence relation.
Lemma 3.1 (Recurrence relation for E(n)). We haveE(n) + E(n − 2) = (n − 2)Fn−3 .

(3.3)

The proof follows from straightforward algebra (see Appendix A of [8]). Solving the recurrence relation yields the following.
Lemma 3.2 (Formula for E(n)). We havenFn−1
E(n) = 2+ O(Fn−2 ).
α +1

(3.4)

The proof follows from using telescoping sums to get an expression for E(n), which is thenevaluated by applying Binet’s formula and differentiating identities (see Appendix A of [8] forthe detailed computations).
Lekkerkerker’s Theorem now follows immediately by substituting the result for E(n) from
Lemma 3.2 into the equation for the mean, (3.1). We have the following result.
Theorem 3.3. The average number of non-consecutive shifted Fibonacci summands used in
representing integers in [Fn , Fn+1 ) is
√
5− 5
2
1
2
E[Kn ] = µn =n− = 2n − = E[Kn ] + 1.
(3.5)
10
5
α +1
5
122

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
0.030
0.025
0.020
0.015
0.010
0.005
0.000
520

540

560

580

600

Figure 1. Plot of the probability p2010 (k) of having exactly k + 1 summandsin the Zeckendorf decompositions of integers in [F2010 , F2011 ) (with pn (k) =n−1−k/Fn−1 ) against the Gaussian with mean µ2010 ≈ 555.55 and variancek
2≈ 179.78.
σ2010
A similar calculation shows the following.
Theorem 3.4. The variance in the number of non-consecutive shifted Fibonacci numbers usedin representing integers in [Fn , Fn+1 ) is
1
2
α
2
=
n−
= Var(Kn ).
Var(Kn ) = σn2 = √ n −255(α + 2)
25
5 5

(3.6)

4. Gaussian Behavior
In the last section we computed the mean by evaluating certain combinatorial sums. We
could similarly derive an explicit formula for the variance, or more generally, any moment.
We choose instead to analyze the density pn (k) in greater detail, and show that it converges
αnpointwise to a Gaussian with mean µn approximately α2n+1 and variance σn2 ≈ 5(α+2). In thecourse of proving this convergence, the mean and the standard deviation naturally fall out of
the calculation. While this does make the previous section superfluous, we chose to include it
as it provides an elementary proof of Lekkerkerker, as well as telling us what the mean andvariance are, which are a great aid in performing the Stirling analysis below. If we didn’t know
µn and σn we would just keep these as initially free parameters, and then choose the values
appropriately to ensure the limits below exist.
Before delving into the proof of Theorem 1.3, we provide some evidence by looking at the
number of summands in the Zeckendorf decomposition for integers in [F2010 , F2011 ) (see Figure1); the fit is visually striking.
4.1. Preliminaries. The computation is a little cleaner if instead of studying the interval[Fn , Fn+1 ) we instead study [Fn+1 , Fn+2 ). The density is nown−k
pn+1 (k) =MAY 2011

k

Fn

.

(4.1)
123

THE FIBONACCI QUARTERLY
We list some useful expansions:µn+1 =
2
σn+1
=

Fn =
We expandn−kkn+ O(1)α+2
αn+ O(1)
5(α + 2)α
√ αn + O ((1 − α)n ) .
5

(4.2)



using Stirling’s formula (see [15] for a proof), which says for large m that


√
1
139
1
m −m
m! = m e
2πm 1 ++−
+ ···12m 288m2 51840m3

 
√
1
= mm e−m 2πm 1 + O
.
(4.3)
m

While we have not proved the variance is of size n, a similar calculation as that for the mean
yields it without any trouble; in the interest of space we merely state the result in Theorem 3.3.
We could also get the right order of magnitude for the variance by the Stirling computationthat follows. As the mean and variance are both of size n, for any fixed  > 0 as n → ∞the set of k with |k − µn+1 | > n1/2+ has negligible probability. This follows by Chebyshev’s
inequality. As we are on the order of n standard deviations from the mean, the probability
is at most O(1/n2 ), which tends to zero with n. Thus we need only worry about analyzing
pn+1 (k) for |k − µn+1 | ≤ n1/2+ . For such k, we have k, n − k and n − 2k are all of size n andhence large, and consequently the first term in Stirling’s formula suffices for our analysis.
After some simple algebra, which includes using Binet’s formula (see (1.1)) for Fn , we find


n−k 1
pn+1 (k) =kFn(n − k)!
1=
k!(n − 2k)! Fn√n−k+ 12
1
(n
−
k)
1
+
O(
)
n−k
1
5



= √

1
1
1
n
k+
1
n−2k+
1
2π k 2 1 + O
2) α · α 1 + O αn(n − 2k)
1 + O(kn−k+ 12√1(n − k)
5
√
1
1
n
k+
n−2k+
2π k 2 (n − 2k)
2 α ·α 1= fn+1 (k) 1 + O
.
n
=

n−2k



 
1
1+O
n

(4.4)

It suffices to analyze fn+1 (k) for |k − µn+1 | ≤ n1/2+ , as the O(1/n) term leads to negligible
changes in the density function. We now split off the terms that exponentially depend on n,
and write
s
√ !

1
(n − k)5(n − k)n−k−n√fn+1 (k) =αkk (n − 2k)n−2k
2π k(n − 2k) α= Nn (k)Sn (k).

124

(4.5)

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
We change variables and replace k with its distance from the mean in units of the standard
deviation, σn+1 . Thus we writek = µn+1 + xσn+1 ,(4.6)

fn+1 (k)dk = fn+1 (µn+1 + σn+1 x)σn+1 dx.

(4.7)

and

Note the change of variables in (4.6) results in dk transforming to σn+1 dx. In these newvariables the main action occurs at x = 0, and the scale is on the order of 1; in other words,
once x is large (such as n ) then we are many standard deviations away and the density is
negligible.
The next few pages present the detailed computation. While the computations are long inplaces, the basic idea (the combinatorial perspective) is straightforward: viewing the problem
combinatorially yields an explicit density function, whose large n asymptotics follow from
Stirling’s formula and careful bookkeeping.
4.2. Analysis of Nn (k).
Lemma 4.1. For any  > 0 we have1
Nn (k) = q· 1 + O n−1/2+ .
2
2πσn+1

(4.8)

1
αn
2
Let C = α+2, so µn+1 = Cn + O(1), and recall σn+1
= 5(α+2)+ O(1). We use a change ofvariable and some algebra to simplify Nn (k) (defined in (4.5)). We set

u=

σn+1
x
x ≈ √  O(n−1/2+ ),
n
n

(4.9)

and find
Nn (k) =
=
=
=

√
n−k
5
k(n − 2k) αs√
1
1 − k/n5√2πn (k/n)(1 − 2k/n) αs√
11 − (µn+1 + σn+1 x)/n
5
√
((µ
+
σ
x)/n)(1
−
2(µ
+
σ
x)/n)
α
2πn
n+1
n+1
n+1
n+1
s
√ 

1
1−C−u
5
1
√
· 1+
,
n
2πn (C + u)(1 − 2C − 2u) α
1
√
2π

s

(4.10)

where the last error arises from replacing µn+1 with Cn + O(1). In fact, as u = O(n−1/2+ )we may drop the u’s at the cost of replacing the error term O(n−1 ) with O(n−1/2+ ). The
following relations help simplify our expression for Nn (k):α + 1 = α2 ,MAY 2011

C=

1
,
α+2

1−C =

α+1
,
α+2

1 − 2C =

α
.
α+2
125

THE FIBONACCI QUARTERLY
αn2Using these, as well as σn+1
= 5(α+2)+ O(1), we find
s
√ 


1
1−C
5
· 1 + O n−1/2+
Nn (k) ≈ √2πn C(1 − 2C) α
r
√


1
(α + 1)(α + 2) 5 · 1 + O n−1/2+
= √
α
α
2πn
r



1
5(α + 2)= √· 1 + O n−1/2+
α
2πn



1
= q
· 1 + O n−1/2+ ,2
2πσn+1(4.11)

2 .
which is recognizable as the normalization constant for a Gaussian with variance σn+1

4.3. Analysis of Sn (k).
Lemma 4.2. For any  > 0 we have Sn (k) = exp(−x2 /2) exp O(n−1/2+3 ) .

Proof. To determine the size of Sn (k) (defined in (4.5)), we take logarithms and once againchange variables by k = µn+1 + xσn+1 . We find(n − k)n−k−nlog Sn (k) = log αkk (n − 2k)n−2k= −n log α + (n − k) log(n − k) − k log k − (n − 2k) log(n − 2k)= −n log α + (n − (µn+1 + xσn+1 )) log(n − (µn+1 + xσn+1 ))− (µn+1 + xσn+1 ) log(µn+1 + xσn+1 )− (n − 2(µn+1 + xσn+1 )) log(n − 2(µn+1 + xσn+1 ))= −n log α



xσn+1
+ (n − (µn+1 + xσn+1 )) log(n − µn+1 ) + log 1 −n − µn+1



xσn+1
− (µn+1 + xσn+1 ) log(µn+1 ) + log 1 +
µn+1



2xσn+1− (n − 2(µn+1 + xσn+1 )) log(n − 2µn+1 ) + log 1 −n − 2µn+1= −n log α
 



n
xσn+1
+ (n − (µn+1 + xσn+1 )) log− 1 + log 1 −µn+1
n − µn+1

xσn+1− (µn+1 + xσn+1 ) log 1 +
µn+1
 



n
2xσn+1− (n − 2(µn+1 + xσn+1 )) log− 2 + log 1 −. (4.12)µn+1
n − 2µn+1

We may simplify the expression above by replacing any µn+1 inside a logarithm with Cn.
This is because the resulting Taylor expansion of the logarithms will yield a term of size 1/n2 .
The largest this can be multiplied by is n, which leads to an error at most O(1/n). We
126

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
exponentiate to get Sn (k), which leads to an error factor of size 1 − exp(O(1/n)), which asn → ∞ is just of size 1/n. We have

 

 
n − µn+1
1−C1n1− 1 = log
= log
+O
= 2 log α + O
,
log
2
µn+1
µn+1
C
n
n2
as (1 − C)/C = α + 1 = α2 . Similarly


 
 
n − 2µn+1
1 − 2Cn1
1− 2 = log
= log
+O
log
= log α + O
.
2
µn+1
µn+1
C
n
n2
Substituting these into (4.12) yields
 
1log Sn (k) + O
n





xσn+1
= −n log α + (n − (µn+1 + xσn+1 )) 2 log α + log 1 −(1 − C)n
xσn+1 − (µn+1 + xσn+1 ) log 1 +
 Cn


2xσn+1.
− (n − 2(µn+1 + xσn+1 )) log α + log 1 −(1 − 2C)n

We note that the coefficient of the log α term is zero, so

 

1
xσn+1
log Sn (k) + O= (n − (µn+1 + xσn+1 )) log 1 −n(1 − C)n
xσn+1 − (µn+1 + xσn+1 ) log 1 +Cn2xσn+1− (n − 2(µn+1 + xσn+1 )) log 1 −(1 − 2C)nxσn+1= ((1 − C)n − xσn+1 )) log 1 −(1 − C)n
xσn+1 − (Cn + xσn+1 ) log 1 +Cn2xσn+1− ((1 − 2C)n − 2xσn+1 )) log 1 −.
(1 − 2C)n(4.13)(4.14)Let u = xσn+1 /n. Note u = O(n−1/2+ ), and thus when we expand the logarithms above,
we never need to keep more than the u2 terms, as anything further will be small, even upon
multiplication by n. Expanding giveslog Sn (k) + O n−1/2+3




u
u2
u
= (1 − C)n −−− un −1−C
2(1 − C)2
1−C




2
u
u
u
−Cn
−
− un
C
2C 2
C




2u
4u2
2u
−(1 − 2C)n −−+ 2un −.
(4.15)
1 − 2C2(1 − 2C)2
1 − 2CMAY 2011

127

THE FIBONACCI QUARTERLY
Note all the un terms cancel, and all that survives are the u2 n terms. Thus
log Sn (k) + O n−1/2+3


1
1
1
1
2
4
= −
+
+
− +
−
u2 n
2(1 − C) 1 − C
2CC
1 − 2C1 − 2Cu2 n.
= −2C − 6C 2 + 4C 3

(4.16)1
αn2
As C = α+2
and u = xσn+1 /n with σn+1
= 5(α+2)+ O(1), simplifying the above yields

and thus exponentiating givesx2
log Sn (k) + O n−1/2+3 = − ,2(4.17)Sn (k) = exp(−x2 /2) exp O(n−1/2+3 ) .

(4.18)


4.4. Proof of Theorem 1.3. Using the results from the previous subsections (Lemmas 4.1
and 4.2, and the change of variable argument on why a factor of σn+1 enters), we can now
prove the convergence to a Gaussian.
Proof of Theorem 1.3. The only item left to prove in Theorem 1.3 is the convergence to theGaussian. We havepn+1 (k)dk = pn+1 (µn+1 + σn+1 x) σn+1 dx= Nn (k)Sn (k)σn+1 1 + O(n−1/2+3 ) dx


1
2
= q
· e−x /2 · σn+1 1 + O(n−1/2+3 ) dx
22πσn+1
12= √e−x /2 1 + O(n−1/2+3 ) dx,
2πwhich clearly converges to the standard normal as n → ∞.

(4.19)


5. Far-difference representations
We now consider the problem of the far-difference representations. We are studying thenumber of positive and negative
shifted Fibonacci summands in the decomposition of integers
P
in [Sn , Sn+1 ), where Sn = 0<n−4i≤n Fn−4i . Using combinatorial arguments as in Lemma 2.1(which involve solving a variant of this Diophantine problem inside a variant of this Diophantine problem), we can come up with a formula for the joint density function pn (k, `) for thenumber of integers in [Sn , Sn+1 ) with exactly k positive Fibonacci summands and exactly `128

VOLUME 49, NUMBER 2

ON THE NUMBER OF SUMMANDS IN ZECKENDORF DECOMPOSITIONS
negative Fibonacci summands. After a lot of algebra, we obtain the formula:
"


k 
X
k−1
`−1
n − 3(k + `) + 2r − 3
pn (k, `) =
k−r
r−2
k+`
r=0


 


`−1
n − 3(k + `) + 2r − 2`−1
n − 3(k + `) + 2r − 1
+
+
r−1
k+`
r−1
k+`


#
` − 1 n − 3(k + `) + 2r
+
.
(5.1)
r
k+`
If we could derive good asymptotics for this formula, we could calculate the limiting density
directly, but this does not seem feasible. With enough patience, this formula can be used to
calculate any particular joint moment, but this approach quickly becomes impractical due tothe combinatorial complexity. Unlike our expression for the standard Fibonacci case, here wehave sums and products of binomial coefficients that would need to be simplified before we
can fruitfully apply Stirling’s formula. As the generating function technique is able to handle
this problem, we invite the reader to see [13] for a complete analysis of this problem.
6. Conclusion and Future Research
Our combinatorial viewpoint has allowed us to extend previous work and obtain Gaussian
behavior for the number of summands for a large class of recurrence relations. This is justthe first of many questions one can ask. Others, which we hope to return to at a later date,include:(1) Lekkerkerker’s Theorem, and the Gaussian extension, are for the behavior in intervals[Fn , Fn+1 ). Do the limits exist if we consider other intervals, say [Fn + g1 (Fn ), Fn +g2 (Fn )) for some functions g1 and g2 ? If yes, what must be true about the growth
rates of g1 and g2 ?
Pn(2) For the generalized
recurrence
relations,what
happens
if
insteadoflookingat
i=1 aiPn
we study i=1 min(1, ai )? In other words, we only care about how many distinct Hi ’s
occur in the decomposition.
(3) What can we say about the distribution of the largest gap between summands in the
Zeckendorf decomposition? Appropriately normalized, how does the distribution ofgaps between the summands behave?
7. Acknowledgement
It is a pleasure to thank our colleagues from the Williams College 2010 SMALL
REU program for many helpful conversations (especially Carlos Dominguez and the
Diophantine Arithmetic and Analysis group of Ed Burger, David Clyde, Cory Colbert,
Gea Shin and Nancy Wang), and Ed Scheinerman and the referee for useful commentsfrom earlier drafts.
References[1] H. Alpert, Differences of multiple Fibonacci numbers, INTEGERS: 9 (2009), 745–749.
[2] E. Burger, personal communication, 2010.
[3] D. E. Daykin, Representation of natural numbers as sums of generalized Fibonacci numbers, J. London
Mathematical Society, 35 (1960), 143–160.
[4] P. Erdsős and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions,
American Journal of Mathematics, 62.1/4 (1940), 738–742.

MAY 2011

129

THE FIBONACCI QUARTERLY[5] A. S. Fraenkel, Systems of numeration, Amer. Math. Monthly, 92.2 (1985), 105–114.
[6] V. E. Hoggatt, Generalized Zeckendorf theorem, The Fibonacci Quarterly, 10.1 (1972), (special issue on
representations), 89–94.
[7] T. J. Keller, Generalizations of Zeckendorfs theorem, The Fibonacci Quarterly, 10.1 (1972), (special issue
on representations), 95–102.
[8] G. Kopp, M. Koloğlu, S. J. Miller, and Y. Wang, On the number of summands in Zeckendorf decompositions,
http://arxiv.org/abs/1008.3204.
[9] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, New York, 2001.
[10] C. G. Lekkerkerker, Voorstelling van natuurlykxe getallen door een som van getallen van Fibonacci, Simon
Stevin, 29 (1951–1952), 190–195.
[11] T. Lengyel, A counting based proof of the generalized Zeckendorf ’s theorem, The Fibonacci Quarterly, 44.4
(2006), 324–325.
[12] S. J. Miller and R. Takloo-Bighash, An Invitation to Modern Number Theory, Princeton University Press,
Princeton, NJ, 2006.
[13] S. J. Miller and Y. Wang, From Fibonacci numbers to central limit type theorems, submitted,
http://arxiv.org/abs/1008.3202.
[14] M. Nathanson, Additive Number Theory: The Classical Bases, Graduate Texts in Mathematics, SpringerVerlag, New York, 1996.
[15] E. Whittaker and G. Watson, A Course of Modern Analysis, 4th edition, Cambridge University Press,
Cambridge, 1996.
[16] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombresde Lucas, Bull. Soc. Roy. Sci. Liége, 41 (1972), 179–182.

MSC2010: 11B39, 65Q30, 60B10
Department of Mathematics and Statistics, Williams College, Williamstown, MA 01267
E-mail address: Murat.Kologlu@williams.edu
Department of Mathematics, University of Chicago, Chicago, IL 60637
E-mail address: gkopp@uchicago.edu
Department of Mathematics and Statistics, Williams College, Williamstown, MA 01267
E-mail address: sjm1@williams.edu, Steven.Miller.MC.96@aya.yale.edu
Department of Mathematics, MIT, Cambridge, MA 02139
E-mail address: yinghui@mit.edu

130

VOLUME 49, NUMBER 2