A SEQUENCE OF BINOMIAL COEFFICIENTS RELATED TO LUCAS AND FIBONACCI NUMBERS

Moussa Benoumhani Mathematical Department Sana’a University P. O. Box 14026 Sana’a Yemen E-mail: benoumhani@yahoo.com

Abstract. Let L(n, k) = \frac{n}{n−k} \binom{n−k}{k}. We prove that all the zeros of the polynomial L_{n}(x) = ∑_{k≥0} L(n, k)x^{k} are real. The sequence L(n, k) is thus strictly log-concave, and hence unimodal

with at most two consecutive maxima. We determine those integers where the maximum is reached. In the last section we prove that L(n, k) satisfies a central limit theorem as well as a local limit theorem.

1. Introduction

A positive real sequence (a_{k})_{k=0}^{n} is said to be unimodal if there exist integers k_{0}, k_{1}, 0 ≤ k_{0} ≤ k_{1} ≤ n such that

a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{k_{0}} = a_{k_{0}+1} = ⋯ = a_{k_{1}} ≥ a_{k_{1}+1} ≥ ⋯ ≥ a_{n}.

The integers l, k_{0} ≤ l ≤ k_{1} are called the modes of the sequence. If k_{0} < k_{1} then (a_{k})_{k=0}^{n} is said to have a plateau of k_{1} − k_{0} + 1 elements; if k_{0} = k_{1} then it is said to have a peak. A real sequence is said to be logarithmically concave (log-concave for short) if

a_{k}^{2} ≥ a_{k−1}a_{k+1}, 1 ≤ k ≤ n − 1 (1)

If the inequalities in (1) are strict, then (a_{k})_{k=0}^{n} is said to be strictly log-concave (SLC for short). A sequence is said to be have no internal zeros if i < j , a_{i} ≠ 0 and a_{j} ≠ 0, then a_{k} ≠ 0 for i ≤ k ≤ j. A log-concave sequence with no internal zeros is obviously unimodal, and if it is SLC, then it has at most two consecutive modes. The following result is sometimes useful in proving log-concavity. For a proof of this theorem, see Hardy and Littlewood [5].

Theorem 1. (I. Newton) Let (a_{k})_{k=0}^{n} be a real sequence. Assume that the polynomial P (x) =

∑_{k=0}^{n} a_{k}x^{k} has only real zeros. Then

a_{k}^{2} ≥ \frac{n − k + 1}{n − k} · \frac{k + 1}{k}a_{k+1}a_{k−1}, 1 ≤ k ≤ n − 1. (2)

If the sequence (a_{k})_{k=0}^{n} is positive and satisfies the hypothesis of the previous theorem, then it is SLC. The two possible values of the modes are given by the next theorem.

Theorem 2. Let (a_{k})_{k=0}^{n} be a real sequence satisfying the hypothesis of the previous theorem. Then every mode of the sequence (a_{k})_{k=0}^{n} satisfies

⌊\frac{∑_{k=1}^{n} ka_{k}}{∑_{k=0}^{n} a_{k}} ⌋ ≤ k_{0} ≤ ⌈\frac{∑_{k=0}^{n} ka_{k}}{∑_{k=0}^{n} a_{k}} ⌉ ,

where ⌊x⌋ and ⌈x⌉ are respectively the floor and the ceiling of x.

For a proof of this theorem, see Benoumhani [2, 3].

Let g(n, k) = \binom{n−k}{k}. This sequence was been investigated by S. Tanny and M. Zuker [8]; they proved that it is SLC, and determined its modes. If r_{n} is the smallest mode of g(n, k), then

r_{n} = ⌈\frac{5n − 3 − \sqrt{5n^{2} + 10n + 9}}{10}⌉ . (3)

They proved that there are infinitely many integers where a double maximum occurs. The integers where this happen are given by: n_{j} = F_{4j} −1, where F_{k} is the k^{th} Fibonacci number. The smallest mode corresponding to n_{j} is given by r_{j} = \frac{1}{5} (L_{4j−1} − 4), where L_{j} is the j’th Lucas number.

In this paper we consider the sequence L(n, k) = \frac{n}{n−k} \binom{n−k}{k}, 0 ≤ k ≤ ⌊\frac{n}{2}⌋, n ≥ 1. It is known that L(n, k) counts the number of ways of choosing k points, no two consecutive, from a collection of n points arranged in a circle; see Stanley [7, p. 73, Lemma 2.3.4] and Sloane [6, A034807].

In Section 2, for the sake of completeness, we prove that all zeros of the polynomials P_{n}(x) = ∑_{k≥0} g(n, k)x^{k} are real. The explicit formula for P_{n}(x) allows us to derive some

identities. Also it enables us to rediscover a result of S. Tanny and M. Zuker. In the third section, we consider the polynomials L_{n}(x) = ∑_{k≥0} L(n, k)x^{k}. We prove that all zeros of L_{n}(x)

are real and negative. In this case, too, the explicit formula for L_{n}(x) gives some identities. The SLC of the sequence L(n, k) is deduced from the fact that L_{n}(x) has real zeros. We determine the modes, and the integers n where L(n, k) has a double maximum. In the last section we prove that the sequence L(n, k) is asymptotically normal, and satisfies a local limit theorem on R.

2. The polynomials P_{n}(x)

It is well known that the sequence g(n, k) = \binom{n−k}{k}, 0 ≤ k ≤ ⌊\frac{n}{2}⌋, is related to the Fibonacci numbers by the relation ∑_{k≥0} \binom{n−k}{k} = F_{n+1} . Recall that the sequence (F_{n}) is defined as follows:

F_{n} = F_{n−1} + F_{n−2}, n ≥ 2,

with F_{0} = 0, F_{1} = 1. Also we have the explicit formula

F_{n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}) .

A SEQUENCE OF BINOMIAL COEFFICIENTS RELATED TO LUCAS AND FIBONACCI NUMBERS 3

It is straightforward to see that P_{n}(x) satisfies the recursion

P_{n}(x) = P_{n−1}(x) + xP_{n−2}(x), (4)

with initial conditions P_{0}(x) = P_{1}(x) = 1. Using the relation (4) we prove Proposition 3. For all n ≥ 0, all zeros of the polynomials P_{n}(x) are real. More precisely, we have P_{n}(x) = \frac{1}{\sqrt{4x+1}} ((\frac{1+\sqrt{4x+1}}{2})^{n+1} − (\frac{1−\sqrt{4x+1}}{2})^{n+1}) . (5)

Proof. Write the relation (4) in matrix form, as follows: ( \begin{matrix}P_{n}(x) \\ P_{n−1}(x) \end{matrix} ) = ( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} ) ( \begin{matrix}P_{n−1}(x) \\ P_{n−2}(x) \end{matrix} ). We deduce

( \begin{matrix}P_{n}(x) \\ P_{n−1}(x) \end{matrix} ) = ( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} )^{n−1} ( \begin{matrix}P_{1}(x) \\ P_{0}(x) \end{matrix} ) = ( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} )^{n−1} ( \begin{matrix}1 \\ 1 \end{matrix} ) .

The eigenvalues of the matrix A = ( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} ) are

λ_{1} = \frac{1 + \sqrt{4x + 1}}{2} , λ_{2} = \frac{1 − \sqrt{4x + 1}}{2},

and two eigenvectors of A are V_{1} = ( \begin{matrix}λ_{1} \\ 1 \end{matrix} )and V_{2} = ( \begin{matrix}λ_{2} \\ 1 \end{matrix} ). Now the matrix A may be written

( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}λ_{1} & λ_{2} \\ 1 & 1 \end{matrix} ) ( \begin{matrix}λ_{1} & 0 \\ 0 & λ_{2} \end{matrix} ) ( \begin{matrix}λ_{1} & λ_{2} \\ 1 & 1 \end{matrix} )^{−1} .

From this, we obtain

( \begin{matrix}1 & x \\ 1 & 0 \end{matrix} )^{n−1} = \frac{1}{λ_{1} − λ_{2}} ( \begin{matrix}λ_{1} & λ_{2} \\ 1 & 1 \end{matrix} ) ( \begin{matrix}λ_{1}^{n−1} & 0 \\ 0 & λ_{2}^{n−1} \end{matrix} ) ( \begin{matrix}1 & −λ_{2} \\ −1 & λ_{1} \end{matrix} )
= \frac{1}{λ_{1} − λ_{2}} ( \begin{matrix}λ_{1}^{n} − λ_{2}^{n} & −λ_{1}^{n}λ_{2} + λ_{1}λ_{2}^{n} \\ λ_{1}^{n−1} − λ_{2}^{n−1} & −λ_{1}^{n−1}λ_{2} + λ_{1}λ_{2}^{n−1} \end{matrix} ) .

The vector ( \begin{matrix}P_{n}(x) \\ P_{n−1}(x) \end{matrix} ) is now

( \begin{matrix}P_{n}(x) \\ P_{n−1}(x) \end{matrix} ) = \frac{1}{λ_{1} − λ_{2}} ( \begin{matrix}λ_{1}^{n} − λ_{2}^{n} & −λ_{1}^{n}λ_{2} + λ_{1}λ_{2}^{n} \\ λ_{1}^{n−1} − λ_{2}^{n−1} & −λ_{1}^{n−1}λ_{2} + λ_{1}λ_{2}^{n−1} \end{matrix} ) ( \begin{matrix}1 \\ 1 \end{matrix} ) .

So,

P_{n}(x) = \frac{1}{λ_{1} − λ_{2}} (λ_{1}^{n} − λ_{2}^{n} − λ_{1}^{n}λ_{2} + λ_{1}λ_{2}^{n}) .

Since λ_{1} + λ_{2} = 1 and λ_{1} − λ_{2} = \sqrt{4x + 1}, we finally obtain

P_{n}(x) = \frac{1}{\sqrt{4x + 1}} ((\frac{1 + \sqrt{4x + 1}}{2})^{n+1} − (\frac{1 − \sqrt{4x + 1}}{2})^{n+1}) .

This is the desired result.

For the roots of P_{n}(x), we have

P_{n}(x) = 0 ⟺ (\frac{1 + \sqrt{4x + 1}}{1 − \sqrt{4x + 1}})^{n+1} = 1 ⟺ (\frac{1 + \sqrt{4x + 1}}{1 − \sqrt{4x + 1}}) = ε_{k}, 1 ≤ k ≤ ⌊\frac{n}{2}⌋

where the ε_{k} are the (n + 1)^{th} roots of unity. Thus,

P_{n}(x) = 0 ⟺ \sqrt{4x + 1} = \frac{ε_{k} − 1}{ε_{k} + 1} ⟺ 4x = −1 + (\frac{ε_{k} − 1}{ε_{k} + 1})^{2} .

Furthermore, we obtain P_{n}(x) = 0 ⟺ x = −\frac{1}{4} (1 + tan^{2} (\frac{kπ}{n+1})) , 1 ≤ k ≤ ⌊\frac{n}{2}⌋ . This proves that the roots of P_{n}(x) are real and negative. □

Remark. In the sequel, we need Lucas numbers. Let us recall their definition:

L_{n} = L_{n−1} + L_{n−2}, L_{0} = 2, L_{1} = 1.

It is not hard to see that

L_{n} = (\frac{1 + \sqrt{5}}{2})^{n} + (\frac{1 − \sqrt{5}}{2})^{n} and L_{n} = F_{n} + F_{n−2},

holds.

Corollary 4. We have the following identities:

1. ∑_{n≥0} P_{n}(x)z^{n} = \frac{1}{1−z−xz^{2}} .

2. ∑_{k≥0}(−1)^{k}\binom{n−k}{k} = \{ \begin{matrix}0, if n = 6k + 2, 6k + 5; \\ 1, if n = 6k, 6k + 1; \\ −1, if n = 6k + 3, 6k + 4. \end{matrix}

3. ∑_{k≥0} k\binom{n−k}{k} = ∑_{k=0}^{n−2} F_{k}F_{n−k−2} = \frac{(n+1)L_{n}−2F_{n}}{5} = \frac{(n−1)F_{n}+(n+1)F_{n−2}}{5} .

4. (n + 1)L_{n} − 2F_{n} = (n − 1)F_{n} + (n + 1)F_{n−2} ≡ 0 (mod 5).

5. ∑_{k≥0}(−1)^{k}k\binom{n−k}{k} = \{ \begin{matrix}\frac{2}{3}n, if n = 6k; \\ \frac{n−1}{3}, if n = 6k + 1; \\ −\frac{n+1}{3}, if n = 6k + 2; \\ −\frac{2n}{3}, if n = 6k + 3; \\ −\frac{(n−1)}{3}, if n = 6k + 4; \\ \frac{n+1}{3}, if n = 6k + 5. \end{matrix}

Proof. The first is known and easy to establish using (4). For (2), put x = −1 in (5). For the third, differentiate the generating function of P_{n}(x) with respect to x, and compare the coefficients, and then put x = 1. Relation 4 is immediate from 3. For the last one, put x = −1 in the derivative of P_{n}(x). □

A SEQUENCE OF BINOMIAL COEFFICIENTS RELATED TO LUCAS AND FIBONACCI NUMBERS 5

According to Theorem 2, every mode r_{n} of the sequence \binom{n−k}{k} satisfies the relation

⌊\frac{∑_{k=1}^{n} k\binom{n−k}{k}}{F_{n}} ⌋ ≤ r_{n} ≤ ⌈\frac{∑_{k=0}^{n} k\binom{n−k}{k}}{F_{n}} ⌉ .

S. Tanny and M. Zuker gave an exact formula for r_{n}, but this is somewhat opaque. So they used another method to give a more explicit one; but it is less precise. Namely, they proved that r_{n} = ⌊\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌋ or r_{n} = ⌈\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌉. We give another proof of this result.

Proposition 5. (S. Tanny, M. Zuker [8])

The modes of the sequences \binom{n−k}{k} are given by r_{n} = ⌊\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌋ or r_{n} = ⌈\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌉ .

Proof. Since all zeros of the polynomial P_{n}(x) are real, it suffices to compute ^{\underline{∑_{k=1}^{n} k\binom{n−k}{k}}} = \frac{∑_{k=1}^{n} k\binom{n−k}{k}}{F_{n}} . The last corollary gives

μ_{n} = \frac{∑_{k=1}^{n} k\binom{n−k}{k}}{F_{n}} = \frac{(n + 1)L_{n} − 2F_{n}}{5F_{n}} = \frac{(n + 1)L_{n}}{5F_{n}} − \frac{2}{5}.

Using the explicit formula for the Lucas and Fibonacci numbers; we obtain

μ_{n} = \frac{(n+1)}{2} (1 − \frac{\sqrt{5}}{5}) \frac{1+a^{n}}{1−a^{n+1}} , a = −\frac{3−\sqrt{5}}{2}.

Now consider the sequence

μ_{n} = \frac{(n+1)}{2} (1 − \frac{\sqrt{5}}{5}) \frac{1+a^{n}}{1−a^{n+1}} − \frac{2}{5} = \frac{(n+1)}{2} (1 − \frac{\sqrt{5}}{5}) A_{n} − \frac{2}{5}, where

A_{n} = \frac{1 + a^{n}}{1 − a^{n+1}} .

Also, observe that for every n we have

A_{2n+1} < 1 < A_{2n}.

So

μ_{2n} = \frac{2n+1}{2} (1 − \frac{\sqrt{5}}{5}) A_{2n} − \frac{2}{5} ≥ \frac{2n+1}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5},

and

μ_{2n+1} = \frac{2n+2}{2} (1 − \frac{\sqrt{5}}{5}) A_{2n+1} − \frac{2}{5} ≤ \frac{2n+2}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5}.

Thus

\frac{2n+1}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5} ≤ μ_{2n} ≤ μ_{2n+1} ≤ \frac{2n+2}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5}.

We deduce that for every n ≥ 2,

\frac{n}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5} ≤ μ_{n} ≤ \frac{n+2}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5}.

Since the difference between the two bounds is (1 − \frac{\sqrt{5}}{5}) < 1; there is a unique integer r_{n} in the interval (\frac{n}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5}, \frac{n+2}{2} (1 − \frac{\sqrt{5}}{5}) − \frac{2}{5}) and of course r_{n} = ⌊\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌋ or r_{n} = ⌈\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌉ . □

3. The polynomials L_{n}(x)

In this section, we consider the sequence L(n, k) = \frac{n}{n−k} \binom{n−k}{k}. We prove that all zeros of the polynomials L_{n}(x) = ∑_{k≥0} L(n, k)x^{k} are real.

Proposition 6. For all n ≥ 2, all zeros of the polynomials L_{n}(x) are real. We have L_{n}(x) = (\frac{1+\sqrt{4x+1}}{2})^{n} + (\frac{1−\sqrt{4x+1}}{2})^{n} . (6).

Proof. Since the polynomials satisfy the recursion

L_{n}(x) = L_{n−1}(x) + xL_{n−2}(x);

with L_{0} = 2, L_{1} = 1, the proof is exactly the same as for P_{n}(x) .

Corollary 7. We have the following identities:

1. ∑_{n≥0} L_{n}(x)z^{n} = \frac{2−z}{1−z−xz^{2}} .

2. ∑_{k≥0} \frac{n}{n−k} \binom{n−k}{k} = L_{n}.

3. ∑_{k≥0}(−1)^{k} \frac{n}{n−k} \binom{n−k}{k} = \{ \begin{matrix}1, if n = 6k + 1 or 6k + 5; \\ −1, if n = 6k + 2 or 6k + 4; \\ 2, if n = 6k; \\ −2, if n = 6k + 3. \end{matrix}

4. ∑_{k=0}^{n−1} L_{k}F_{n−k−1} = nF_{n}.

Proof. Relation (1) is immediate, for the second one, it suffices to put x = 1 in (6). For the third one, put x = −1 again in (6). The last one is obtained by differentiating the generating function of L_{n}(x) with respect to x and then equating the coefficients of z^{n} in both sides. □

Since all zeros of the polynomials L_{n}(x) are real, it follows that the sequence L(n, k) is SLC. We follow S. Tanny and M. Zuker to give the modes.

Theorem 8. The smallest mode of the sequence L(n, k) is given by

k_{n} = ⌈\frac{5n − 4 − \sqrt{5n^{2} − 4}}{10}⌉ .

Proof. The integer k_{n} satisfies

\{ \begin{matrix}L(n, k_{n} − 1) < L(n, k_{n})  (a) \\ L(n, k_{n}) ≥ L(n, k_{n} + 1)  (b) \end{matrix}

Let

f(x) = 5x^{2} − (5n + 6)x + n^{2} + 3n + 2,

and

g(x) = 5x^{2} − (5n − 4)x + n^{2} + 2n + 1.

We have

(a) ⟺ f(k_{n}) > 0;
(b) ⟺ g(k_{n}) ≤ 0.

The roots of the first equation are \frac{5n+6±\sqrt{5n^{2}−4}}{10}, and those of the second one are \frac{5n−4±\sqrt{5n^{2}−4}}{10}. The desired integer satisfies

\frac{5n − 4 − \sqrt{5n^{2} − 4}}{10} ≤ k_{n} < \frac{5n + 6 − \sqrt{5n^{2} − 4}}{10}.

Which is what we wanted. □

The previous formula for k_{n} is not as explicit as expected. We give a more explicit one.

Corollary 9. The integer k_{n} satisfies the following k_{n} = ⌊\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌋ or k_{n} = ⌈\frac{n}{2} (1 − \frac{\sqrt{5}}{5})⌉ .

Proof. The proof is the same as for r_{n} . □

In the next result, the integers n, such that the sequence L(n, k) has a double maximum will be determined. Before determining these integers, we need the following lemmas:

Lemma 10. For every n ≥ 0, 5F_{n}^{2} + 4(−1)^{n} = L_{n}^{2}.

Proof. This is known, and straightforward using the explicit formulas of F_{n} and L_{n} . □

Lemma 11. For every n ≥ 0, 5F_{4n+1} − L_{4n+1} − 4 ≡ 0 (mod 10).

Proof. Again, the explicit formulas of F_{n} and L_{n} give easily the wanted result. □

Theorem 12. The sequence L(n, k) has a double maximum if and only if n = F_{4j+1}, and in this case the smallest mode is given by k_{n} = F_{2j}^{2}.

Proof. If l is the smallest mode of L(n, k) then it satisfies

L(n, l) = L(n, l + 1),

which is equivalent to

f(n, l) = 5l^{2} − (5n − 4)l + n^{2} − 2n + 1 = 0 . (7)

Equation (7) has two roots in l

l_{1, 2} = \frac{5n − 4 ± \sqrt{5n^{2} − 4}}{10}.

The solution greater than \frac{n}{2} is rejected, since the modes of L(n, k) are less than \frac{n}{2}. The smallest one remains, i.e.,

l = \frac{5n − 4 − \sqrt{5n^{2} − 4}}{10} . (8)

So, we are looking for all pairs of integers (n_{j}, k_{j}), 0 ≤ k_{j} ≤ \frac{n_{j}}{2} , satisfying (7) (or (8)). We may transform (8) to an equation related to Pell’s equation as in Tanny and Zuker [8], and then use some classical facts about units (invertible elements) in quadratic fields (see Cohn [4] for details). But we proceed differently: by Lemma 10, 5F_{2j+1}^{2} − 4 = L_{2n+1}^{2},

and by Lemma 11, 5F_{4j+1} − 4 − \sqrt{5F_{4j+1}^{2} − 4} ≡ 5F_{4j+1} − 4 − L_{4j+1} ≡ 0 (mod 10), that

is, k_{j} = ^{\frac{55F_{4j+1}−4±\sqrt{5F_{4j+1}^{2}−4}}{10}} = \frac{5F_{4j+1}−4−L_{4j+1}}{10} = F_{2j}^{2} ≤ \frac{F_{4j+1}}{2} . So, some of the Fibonacci numbers are certainly among the n_{j}. Now let (n_{0}, k_{0}) = (1, 0), (n_{1}, k_{1}) = (5, 1), (n_{2}, k_{2}) = (34, 9), (n_{3}, k_{3}) = (233, 64), ...,with n_{j} = F_{4j+1}, k_{j} = F_{2j}^{2}. The following recursions are easily derived:

\{ \begin{matrix}n_{j+1} = 7n_{j} − n_{j−1}; \\ k_{j+1} = 7k_{j} − k_{j−1} + 2 . \end{matrix} (9)

Now, we prove that all solutions of (7) are in fact (n_{j} = F_{4j+1}, k_{j} = F_{2j}^{2})_{j≥0}. We will show that if (n_{j}, k_{j}) is a solution of (7), then

(n_{j+1}, k_{j+1}) = (7n_{j} − n_{j−1}, 7k_{j} − k_{j−1} + 2)

is another one. Indeed

f(n_{j+1}, k_{j+1}) = 5k_{j+1}^{2} − (5n_{j+1} − 4)k_{j+1} + n_{j+1}^{2} − 2n_{j+1} + 1
= 5(7k_{j} − k_{j−1} + 2)^{2} − (5(7n_{j} − n_{j−1}) − 4)(7k_{j} − k_{j−1} + 2)
+(7n_{j} − n_{j−1})^{2} − 2(7n_{j} − n_{j−1}) + 1
= 0

since f(n_{i}, k_{i}) = 5k_{i}^{2} − (5n_{i} − 4)k_{i} + n_{i}^{2} − 2n_{i} + 1 = 0 for 0 ≤ i ≤ j. Suppose that (n, k) is another one, 0 ≤ k ≤ \frac{n}{2}; different from those (n_{j}, k_{j}). There is a unique (n_{i}, k_{i}) such that n_{i} < n < n_{i+1}. We verify easily that f(7n − n_{i−1}, 7k − k_{i−1} + 2) = 0. This means that (n, k) = (n_{i}, k_{i}), and proves that all the solutions of (7) are given by the recursions (9).This ends the proof. □

Remarks. 1. There is a relation between the modes of the sequence g(n, k) and those of L(n, k). Let (m_{j}, r_{j}) be the sequence of integers such that g(m_{j}, r_{j}) = g(m_{j}, r_{j} + 1). Since m_{j} = F_{4j} − 1,and r_{j} = \frac{1}{5}(L_{4j−1} − 4), it is easy to establish (by direct calculations, or generating functions of r_{j} ), that

\{ \begin{matrix}n_{j} = r_{j+1} − r_{j}; \\ k_{j} = m_{j} − 2r_{j} − 1. \end{matrix}

2. Note that our relation for k_{j} was derived by S. Tanny and M. Zuker [9, p. 301]. There, the initial conditions for the Fibonacci numbers are: F_{0} = F_{1} = 1.

3. Using the recursions (9), we obtain the generating functions:

g(x) = ∑_{j=0}^{∞} n_{j}x^{j} = \frac{1 − 2x}{1 − 7x + x^{2}} and h(x) = ∑_{j=1}^{∞} k_{j}x^{j} = \frac{x + x^{2}}{(1 − x)(1 − 7x + x^{2})}.

4. A central and a local theorem for L(n, k)

A positive real sequence a(n, k)_{k=0}^{n}, with A_{n} = ∑_{k=0}^{n} a(n, k) ≠ 0, is said to satisfy a central

limit theorem (or is asymptotically normal) with mean μ_{n} and variance σ_{n}^{2} if

lim_{n⟶+∞} sup_{x∈R} | ∑_{0≤k≤μ_{n}+xσ_{n}} \frac{a(n, k)}{A_{n}} − (2π)^{−1/2} ∫_{−∞}^{x} e^{− \frac{t^{2}}{2}} dt| = 0.

The sequence satisfies a local limit theorem on B ⊆ R ; with mean μ_{n} and variance σ_{n}^{2} if

lim_{n⟶+∞} sup_{x∈B} |\frac{σ_{n}a(n, μ_{n} + xσ_{n})}{A_{n}} − (2π)^{−1/2}e^{− \frac{x^{2}}{2}} | = 0.

Recall the following result (see Bender [1]).

Theorem 13. Let (P_{n})_{n≥1} be a sequence of real polynomials; with only real negative zeros. The sequence of the coefficients of the (P_{n})_{n≥1} satisfies a central limit theorem; with μ_{n} =

\frac{P_{n}^{”}(1)}{P_{n}(1)} and σ_{n}^{2} = (\frac{P_{n}^{”}(1)}{P_{n}(1)} + \frac{P′_{n}(1)}{P_{n}(1)} − (\frac{P′_{n}(1)}{P_{n}(1)})^{2}) provided that lim_{n⟶+∞} σ_{n}^{2} = +∞. If, in addition,

the sequence of the coefficients of each P_{n} is with no internal zeros; then the sequence of the coefficients satisfies a local limit theorem on R.

The fact that the zeros of the sequence L_{n}(x) are real implies the following result.

Theorem 14. The sequence (L(n, k))_{k≥0} satisfies a central limit and a local limit theorem on R with μ_{n} = \frac{L_{n}^{”}(1)}{L_{n}(1)} ∼ \frac{n}{2} (1 − \frac{\sqrt{5}}{5})and σ_{n}^{2} = \frac{L_{n}^{”}(1)}{L_{n}(1)} + \frac{L′_{n}(1)}{L_{n}(1)} − (\frac{L′_{n}(1)}{L_{n}(1)}) ∼ 5^{− \frac{3}{4}} n

Proof. We have

σ_{n}^{2} = \frac{L_{n}^{”}(1)}{L_{n}(1)} + \frac{Ln^{′}(1)}{L_{n}(1)} − (\frac{Ln^{′}(1)}{L_{n}(1)})^{2} = \frac{n^{2}L_{n−2}L_{n} − 5n^{2}F_{n−1}}{5L_{n}^{2}} + \frac{3nF_{n−1} − nL_{n−2}}{5L_{n}} .

Let α = \frac{1+\sqrt{5}}{2}, β = \frac{1−\sqrt{5}}{2}. Using the explicit formulas of L_{n} and F_{n}, we obtain

σ_{n}^{2} = \frac{(−1)^{n}n^{2}}{α^{2n} + β^{2n} + 2(−1)^{n}} + \frac{α^{n−2} (\frac{3\sqrt{5}α}{5} − 1) n − β^{n−2} (\frac{3\sqrt{5}β}{5} + 1) n}{5 (α^{n} + β^{n})} ∼ 5^{− \frac{3}{4}} n.

So, lim_{n⟶+∞} σ_{n} = +∞. The local limit theorem is then easily seen to be satisfied; since L(n, k) ≠

0, for 0 ≤ k ≤ ⌊\frac{n}{2}⌋ . □

As a consequence of the local limit theorem, we have

Corollary 15. Let L = max\{L(n, k), 0 ≤ k ≤ \frac{n}{2}\}. Then

L ∼ \frac{5^{\frac{3}{4}} (\frac{1+\sqrt{5}}{2})^{n}}{\sqrt{2πn}} .

Acknowledgments: My sincere thanks to Andreas Dress and Jean-Louis Nicolas for their valuable corrections and comments.

References

[1] E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory, Ser. A 15 (1973), 91–111.

[2] M. Benoumhani, Polynômes à racines réelles et applications combinatoires, Thèse de doctorat, Université Claude Bernard, Lyon 1, Lyon, France.1993.

[3] M. Benoumhani, Sur une propriété des polynômes à racines négatives, J. Math. Pures Appl, 75 (1996), 85–105.

[4] H. Cohn, A Classical Invitation to Algebraic Numbers and Class Fields, Springer-Verlag, 1978.

[5] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge Univ. Press, 1956.

[6] N. Sloane, Online Encyclopedia of Integer Sequences, www.research.att.com/~njas/sequences/index.html.

[7] R. Stanley, Enumerative Combinatorics, Wadsworth & Brooks / Cole, Monterey, California 1986.

[8] S. Tanny and M. Zuker, On a unimodal sequence of binomial coefficients, Discrete Math. 9 (1974), 79–89.

[9] S. Tanny and M. Zuker, Analytic methods applied to a sequence of binomial coefficients, Discrete Math. 24 (1978), 299–310.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11B65. Keywords: Fibonacci number, log–concave sequence, limit theorems, Lucas number, polynomial with real zeros, unimodal sequence.

(Concerned with sequence \underline{A034807}.)

Received December 21, 2002; revised version received April 25, 2002. Published in Journal of Integer Sequences, June 5, 2003.

Return to Journal of Integer Sequences home page.