Families of Sequences From a Class of Multinomial Sums

Martin Griffiths Department of Mathematical Sciences University of Essex Colchester CO4 3SQ United Kingdom

                  griffm@essex.ac.uk

Abstract

In this paper we obtain formulas for certain sums of products involving multinomial coefficients and Fibonacci numbers. The sums studied here may be regarded as generalizations of the binomial transform of the sequence comprising the even-numbered terms of the Fibonacci sequence. The general formulas, involving both Fibonacci and Lucas numbers, give rise to infinite sequences that are parameterized by two positive integers. Links to the exponential partial Bell polynomials are also established.

1 Introduction

The sequences being considered in much of what follows may in some sense be regarded as generalizations of the binomial transform {b_{n}} of {F_{2n}}, where the nth Fibonacci number F_{n} may be defined recursively by setting F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2 [2, 3, 5]. The nth term of {b_{n}} is given by

b_{n} = ∑_{k=0}^{n} \binom{n}{k}F_{2k}.  (1)

This sequence, which starts 1, 5, 20, 75, 275, …, appears in Sloane’s On-line Encyclopedia of Integer Sequences [10] as \underline{A093131}. It may be shown that

b_{2n−1} = 5^{n−1}L_{2n−1} and b_{2n} = 5^{n}F_{2n},  (2)

where L_{n}, the nth Lucas number, is defined by L_{0} = 2, L_{1} = 1 and L_{n} = L_{n−1} + L_{n−2} for n ≥ 2.

Our generalization leads us to study certain sums of products involving multinomial coefficients and Fibonacci numbers. These give rise to sequences parameterized by two positive integers, s and t. In other words, each pair (s, t) is associated with a particular infinite sequence. Note, by way of contrast, that {b_{n}} does not possess any parameters. A further result concerning 1-parameter sequences is then derived. Finally, we go on to obtain some results associated with our sequences, including one in connection with the exponential partial Bell polynomials.

2 Some general results

Throughout this paper we use the notation

\binom{n}{a_{0}, a_{2}, …, a_{t−1}}

to represent the multinomial coefficient [6]

\frac{(a_{0} + a_{2} + ⋯ + a_{t−1})!}{a_{0}!a_{1}! ⋯ a_{t−1}!},

where each a_{i}, i = 0, 1, …, t − 1, is a non-negative integer such that n = a_{0} + a_{1} + ⋯ + a_{t−1}. The binomial coefficients correspond to the special case t = 2.

Furthermore, we shall find it useful to extend the definition of the Fibonacci numbers to negative subscripts as in [5]. This may be achieved by rearranging the Fibonacci recurrence relation to give F_{n−2} = F_{n} − F_{n−1} and then using it in a recursive manner for n = 1, 0, −1, −2 . . .. From this we obtain F_{−1} = F_{1} − F_{0} = 1, F_{−2} = F_{0} − F_{−1} = −1, and so on. It is in fact straightforward to show that for any n ∈ ℕ,

F_{−n} = (−1)^{n+1}F_{n}.  (3)

In order to obtain some of the results that follow, we will, at appropriate points, introduce and utilize various mathematical properties of the golden ratio ϕ [4, 5, 6], where

ϕ = \frac{1 + \sqrt{5}}{2}.

We shall have cause to make frequent use of the result

ϕ^{j} = F_{j}ϕ + F_{j−1},  (4)

which is given in [5, 6]. This may be proved by induction using the Fibonacci recurrence relation and the fact that ϕ^{2} = ϕ + 1. Note, by virtue of (3) and the result \frac{1}{ϕ} = ϕ − 1, that (4) is valid for all j ∈ ℤ. Similarly, we may obtain

L_{−n} = (−1)^{n}L_{n}  (5)

and

\sqrt{5} ϕ^{j} = L_{j}ϕ + L_{j−1}.  (6)

Result (6) appears in [5] and, as with (4), is valid for all j ∈ ℤ.

In Theorem 2 below, use shall be made of the following simple Lemma concerning irrational numbers in general:

Lemma 1. For any irrational number α and p, q, r, s ∈ ℚ, pα + r = qα + s if, and only if, p = q and r = s.

Proof. Suppose that pα + r = qα + s. If p = q then it is clear that r = s. Let us assume, therefore, that p ≠ q. We then can write

α = \frac{s − r}{p − q} ∈ ℚ.

This, however, is a contradiction since α is irrational. It must thus be the case that pα + r = qα + s implies p = q and r = s. The converse is obviously true, thereby proving the lemma.

Theorem 2.

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}}F_{u_{1}(k,m)} = F_{2kn(2m−1)} (\frac{F_{4km}}{F_{2k}} )^{n} ,

where

u_{1}(k, m) = 4k (a_{1} + 2a_{2} + ⋯ + (2m − 1)a_{2m−1})

and the summation is to be taken over all possible a_{i} ≥ 0, i = 0, 1, 2, …, 2m − 1, such that a_{0} + a_{1} + ⋯ + a_{2m−1} = n.

Proof. First, let

g(s, t) = 1 + ϕ^{2s} + ϕ^{4s} + ⋯ + ϕ^{2s(t−1)}

= ∑_{j=0}^{t−1} ϕ^{2js},

where s, t ∈ ℕ such that t ≥ 2. Then, on using (4), it follows that for any n ∈ ℕ we have

[g(2k, 2m)]^{n} = ∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}} (ϕ^{4k})^{a_{1}} (ϕ^{8k})^{a_{2}} ⋯ (ϕ^{4k(2m−1)})^{a_{2m−1}}
= ∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}}ϕ^{4k(a_{1}+2a_{2}+···+(2m−1)a_{2m−1})}  (7)
= ∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}} (F_{u_{1}(k,m)}ϕ + F_{u_{1}(k,m)−1}) ,  (8)

where u_{1}(k, m) is as in the statement of the theorem, and the summation is to be taken over all possible a_{i} ≥ 0, i = 0, 1, 2, …, 2m − 1, such that a_{0} + a_{1} + ⋯ + a_{2m−1} = n.

Next, on using the formula for the sum of a finite geometric progression [9], we have

g(s, t) = \frac{(ϕ^{2s})^{t} − 1}{ϕ^{2s} − 1}

= \frac{ϕ^{st} (ϕ^{st} − ϕ^{−st})}{ϕ^{s} (ϕ^{s} − ϕ^{−s})}

= ϕ^{s(t−1)} (\frac{ϕ^{st} − ϕ^{−st}}{ϕ^{s} − ϕ^{−s}} ) .  (9)

From Binet’s formula [2, 3, 4, 5, 6]

F_{j} = \frac{1}{\sqrt{5}} (ϕ^{j} − (−\frac{1}{ϕ})^{j})

and the corresponding formula for the Lucas numbers [2, 4]

L_{j} = ϕ^{j} + (−\frac{1}{ϕ})^{j}

we may obtain the result

ϕ^{j} − ϕ^{−j} = \begin{cases}\sqrt{5} F_{j}, & if j is even; \\ L_{j}, & if j is odd. \end{cases}  (10)

This implies, by way of (9), that

g(2k, 2m) = ϕ^{2k(2m−1)} \frac{F_{4km}}{F_{2k}} ,

and hence, using (4), that

[g(2k, 2m)]^{n} = ϕ^{2kn(2m−1)} (\frac{F_{4km}}{F_{2k}} )^{n}  (11)
= (ϕF_{2kn(2m−1)} + F_{2kn(2m−1)−1}) (\frac{F_{4km}}{F_{2k}} )^{n} .  (12)

The theorem then follows from (8), (12) and Lemma 1 with α = ϕ.

In the following corollary we show how to generalize the result from Theorem 2 yet further: Corollary 3. For any j ∈ ℤ,

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}}F_{u_{1}(k,m)+j} = F_{2kn(2m−1)+j} (\frac{F_{4km}}{F_{2k}} )^{n} ,

where the notation is identical to that used in the statement of Theorem 2.

Proof. From (7) and (11), we obtain

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}}ϕ^{4k(a_{1}+2a_{2}+···+(2m−1)a_{2m−1})} = ϕ^{2kn(2m−1)} (\frac{F_{4km}}{F_{2k}} )^{n} .

Both sides of this equality are then multiplied by ϕ^{j} for some j ∈ ℤ, and the result follows from (4) and Lemma 1.

Similarly, (9) and (10) give

g(2k − 1, 2m) = ϕ^{(2k−1)(2m−1)} \frac{\sqrt{5} F_{2m(2k−1)}}{L_{2k−1}} ,  (13)
g(2k, 2m − 1) = ϕ^{4k(m−1)} \frac{F_{2k(2m−1)}}{F_{2k}} ,  (14)
g(2k − 1, 2m − 1) = ϕ^{2(2k−1)(m−1)} \frac{L_{(2k−1)(2m−1)}}{L_{2k−1}} .  (15)

On obtaining the multinomial expansions for [g(2k, 2m − 1)]^{n} and [g(2k − 1, 2m − 1)]^{n}, using (14) and (15), and then employing a similar idea to that utilized in Corollary 3, we have the following results:

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−2}}F_{u_{3}(k,m)+j} = F_{4kn(m−1)+j} (\frac{F_{2k(2m−1)}}{F_{2k}} )^{n}  (16)

and

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−2}}F_{u_{4}(k,m)+j} = F_{2n(2k−1)(m−1)+j} (\frac{L_{(2k−1)(2m−1)}}{L_{2k−1}} )^{n} ,  (17)

where

u_{3}(k, m) = 4k (a_{1} + 2a_{2} + ⋯ + (2m − 2)a_{2m−2})

and

u_{4}(k, m) = 2(2k − 1) (a_{1} + 2a_{2} + ⋯ + (2m − 2)a_{2m−2}) .

The presence of the factor \sqrt{5} in (13) means that, in order to use Lemma 1, a slightly different treatment is required. We use (4) and (6) to obtain

[g(2k − 1, 2m)]^{2n−1} = 5^{n−1}\sqrt{5} ϕ^{(2n−1)(2k−1)(2m−1)} (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n−1}

= 5^{n−1} (L_{(2n−1)(2k−1)(2m−1)}ϕ + L_{(2n−1)(2k−1)(2m−1)}) (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n−1}

and

[g(2k − 1, 2m)]^{2n} = 5^{n}ϕ^{2n(2k−1)(2m−1)} (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n}

= 5^{n} (F_{2n(2k−1)(2m−1)}ϕ + F_{2n(2k−1)(2m−1)}) (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n} .

These results lead to

∑ \binom{2n − 1}{a_{0}, a_{1}, …, a_{2m−1}}F_{u_{2}(k,m)+j} = 5^{n−1}L_{(2n−1)(2k−1)(2m−1)+j} (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n−1}  (18)

and

∑ \binom{2n}{a_{0}, a_{1}, …, a_{2m−1}}F_{u_{2}(k,m)+j} = 5^{n}F_{2n(2k−1)(2m−1)+j} (\frac{F_{2m(2k−1)}}{L_{2k−1}} )^{2n} ,  (19)

respectively, where

u_{2}(k, m) = 2(2k − 1) (a_{1} + 2a_{2} + ⋯ + (2m − 1)a_{2m−1}) .

Note that a formula for the right-hand side of (1) may be obtained by considering the expansion of (1 + ϕ^{2})^{n} = [g(1, 2)]^{n}. The results b_{2n−1} = 5^{n−1}L_{2n−1} and b_{2n} = 5^{n}F_{2n} given in (2) may thus be seen to be specializations of (18) and (19), respectively. It is also worth noting, for example, that both Identity 3 in [1] and Result (31) in [7] are specializations of Theorem 2. The sequence arising from Identity 3 in [1] appears in [10] as \underline{A087426}.

Since

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−1}}F_{u_{1}(k,m)}

is an integer, it follows from Theorem 2 that

F_{2k}^{n}|F_{2kn(2m−1)}F_{4km}^{n}.

Although not necessarily following from this divisibility result, it is in fact well-known that F_{a}|F_{ab} and hence F_{a}^{n}|F_{ab}^{n} for any a, b, n ∈ ℕ [2]. Indeed, a similar observation may be made regarding (16). On considering (17) we see that

L_{2k−1}^{n}|F_{2n(2k−1)(m−1)}L_{(2k−1)(2m−1)}^{n}.

Again, although not necessarily following from this, it is true, if rather less well-known, that L_{a}|L_{ab} for any odd positive integers a and b. Similarly, (18) and (19) hint at the possibility that, for any odd positive integer a and even positive integer b, L_{a}|F_{ab}. This result also happens to be true (see [5] for a summary of such results).

Leading on from this, since

\frac{F_{2k(2m−1)}}{F_{2k}} = 1 + ∑_{j=1}^{m−1} L_{4jk}  and  \frac{L_{(2k−1)(2m−1)}}{L_{2k−1}} = 1 + ∑_{j=1}^{m−1} L_{2j(2k−1)},

we may in fact combine (16) and (17) to give

∑ \binom{n}{a_{0}, a_{1}, …, a_{2m−2}}F_{u_{5}(s,m)+j} = F_{2sn(m−1)+j} (1 + ∑_{j=1}^{m−1} L_{2js})^{n} ,

where

u_{5}(s, m) = 2s (a_{1} + 2a_{2} + ⋯ + (2m − 2)a_{2m−2})

We have thus combined two cases at the expense of a somewhat more unwieldy expression on the right-hand side.

3 An alternative family of sequences

We now consider a family of sequences parameterized by t ∈ ℕ such that t is even, noting that these are not specializations of any of the sequences derived in Section 2. Let us start by defining the expression h(t) given by

h(t) = 1 + ϕ + ϕ^{2} + ⋯ + ϕ^{(t−1)}.

Then, since ϕ = \frac{1}{ϕ−1}, we may obtain

h(4m) = \frac{ϕ^{4m} − 1}{ϕ − 1}

= ϕ · ϕ^{2m} (ϕ^{2m} − ϕ^{−2m})

= ϕ^{2m+1} (ϕ^{2m} − (−\frac{1}{ϕ})^{2m})

= ϕ^{2m+1}\sqrt{5} F_{2m},  (20)

and similarly

h(4m − 2) = ϕ^{2m} (ϕ^{2m−1} + (−\frac{1}{ϕ})^{2m−1})
= ϕ^{2m}L_{2m−1}.  (21)

Result (20) gives rise to

∑ \binom{2n − 1}{a_{0}, a_{1}, …, a_{4m−1}}F_{v_{1}(m)+j} = 5^{n−1}L_{(2n−1)(2m+1)+j}F_{2m}^{2n−1}

and

∑ \binom{2n}{a_{0}, a_{1}, …, a_{4m−1}}F_{v_{1}(m)+j} = 5^{n}F_{2n(2m+1)+j}F_{2m}^{2n},

while (21) leads to

∑ \binom{n}{a_{0}, a_{1}, …, a_{4m−3}}F_{v_{2}(m)+j} = F_{2mn+j}L_{2m−1}^{n},  (22)

where

v_{1}(m) = a_{1} + 2a_{2} + ⋯ + (4m − 1)a_{4m−1}

and

v_{2}(m) = a_{1} + 2a_{2} + ⋯ + (4m − 3)a_{4m−3}.

4 Further results

As we now show, it is possible to express (22) in a form such that the subscripts of the Fibonacci numbers are given explicitly. On treating (1 + x + x^{2} + ⋯ + x^{t−1})^{n} as a formal power series and ignoring issues of convergence, we have

(1 + x + x^{2} + ⋯ + x^{t−1})^{n} = (\frac{1 − x^{t}}{1 − x} )^{n}

= (1 − x^{t})^{n} (1 − x)^{−n}

= ∑_{i=0}^{n} \binom{n}{i} (−x^{t})^{i} ∑_{j=0}^{∞} \binom{n − 1 + j}{n − 1}x^{j}.

Our aim is to find the coefficient of x^{r} in the above product of sums. To this end, consider the following typical term that arises when the product is expanded:

(−1)^{i}\binom{n}{i}\binom{n − 1 + j}{n − 1}x^{ti+j}.

It is clear from this that

(−1)^{i}\binom{n}{i}\binom{n − 1 + j}{n − 1}

makes a non-zero contribution to the coefficient of x^{r} if, and only if, 0 ≤ i ≤ ⌊\frac{r}{t}⌋. The coefficient of x^{r} is thus

\begin{matrix}⌊ & \frac{r}{t} & ⌋ \\ ∑ \\ i=0 \end{matrix}(−1)^{i}\binom{n}{i}\binom{n − 1 + r − ti}{n − 1}.

In conjunction with (22) this then leads to the result

∑_{r=0}^{n(4m−3)} \begin{matrix}⌊ & \frac{r}{4m−2} & ⌋ \\ & ∑ \\ & i=0 \end{matrix}(−1)^{i}\binom{n}{i}\binom{n − 1 + r − i(4m − 2)}{n − 1}F_{r+j} = F_{2mn+j}L_{2m−1}^{n}

for any j ∈ ℤ.

Finally, we demonstrate a connection between the results obtained in Section 2 and the exponential partial Bell polynomials B_{k,n} [8, 11]. The latter are defined by way of

∑_{k=n}^{∞} B_{k,n} (x_{1}, x_{2}, …) \frac{t^{k}}{k!} = \frac{1}{n!} (∑_{j=1}^{∞} \frac{t^{j}}{j!}x_{j})^{n} .

There are a number of well-known results associated with these polynomials. For example,

∑_{k=n}^{∞} B_{k,n} (1, 1, 1, …) \frac{t^{k}}{k!} = \frac{1}{n!} (∑_{j=1}^{∞} \frac{t^{j}}{j!})^{n}

= \frac{1}{n!} (e^{t} − 1)^{n} ,

which is the exponential generating function for the nth column of the Stirling number triangle of the second kind. Incidentally, it follows from this that

B_{k,n}(1, 1, 1, …) = S(k, n),

the Stirling number of the second kind enumerating the ways of partitioning a set of k labeled objects into n non-empty disjoint parts. In addition, the kth Bell number B_{k} arises by way of

∑_{n=1}^{k} B_{k,n}(1, 1, 1, …) = B_{k}.

This number enumerates all possible partitions of k labeled objects.

We obtain here the result

∑_{k=2n−1}^{∞} B_{k,2n−1} (1!, 2!, …, (4m)!, 0, 0, …) \frac{F_{k+j}}{k!} = \frac{5^{n−1}}{(2n − 1)!}L_{2(m+1)(2n−1)+j}F_{2m}^{2n−1}  (23)

for any j ∈ ℤ, noting that the left-hand side is in fact a finite sum. First, with the help of (10):

∑_{k=2n−1}^{∞} B_{k,2n−1} (1!, 2!, …, (4m)!, 0, 0, …) \frac{ϕ^{k}}{k!} = \frac{1}{(2n − 1)!} (∑_{j=1}^{4m} \frac{ϕ^{j}}{j!} j!)^{2n−1}

= \frac{ϕ^{2n−1}}{(2n − 1)!} ( ∑_{j=0}^{4m−1} ϕ^{j})^{2n−1}

= \frac{ϕ^{2n−1}}{(2n − 1)!} (\frac{ϕ^{4m} − 1}{ϕ − 1})^{2n−1}

= \frac{ϕ^{4n−2}}{(2n − 1)!} (ϕ^{2m} (ϕ^{2m} − ϕ^{−2m}))^{2n−1}

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

Then, on utilizing Lemma 1, (6) and the idea from Corollary 3, we obtain (23). Similarly,

∑_{k=2n}^{∞} B_{k,2n} (1!, 2!, …, (4m)!, 0, 0, …) \frac{F_{k+j}}{k!} = \frac{5^{n}}{(2n)!}F_{4n(m+1)+j}F_{2m}^{2n}

and

∑_{k=n}^{∞} B_{k,n} (1!, 2!, …, (4m − 2)!, 0, 0, …) \frac{F_{k+j}}{k!} = \frac{1}{n!}F_{n(2m+1)+j}L_{2m−1}^{n}.

5 Acknowledgement

The author wishes to thank the referee for a number of comments and suggestions that have led to improvements in this paper.

References

[1] A. T. Benjamin, A. K. Eustis, and S. S. Plott, The 99th Fibonacci identity, Electron. J. Combin. 15 (2008), #R34.

[2] D. Burton, Elementary Number Theory, McGraw-Hill, 1998.

[3] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[4] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.

[5] R. Knott, Fibonacci and golden ratio formulae,

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html,

2011.

[6] D. E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, 1968.

[7] J. W. Layman, Certain general binomial-Fibonacci sums, Fibonacci Quart. 15 (1977), 362–366.

[8] M. Mihoubi, Partial Bell polynomials and inverse relations, J. Integer Seq. 13 (2010), Article 10.4.5.

[9] A. J. Sadler and D. W. S. Thorning, Understanding Pure Mathematics, Oxford University Press, 1987.

[10] N. J. A. Sloane (Ed.), The On-Line Encyclopedia of Integer Sequences,

http://oeis.org/, 2011.

[11] Wikipedia contributors, Bell polynomials, Wikipedia, The Free Encyclopedia,

http://en.wikipedia.org/wiki/Bell polynomials, 2011.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 05A10.

Keywords: multinomial coefficient, Fibonacci number, Lucas number, partial Bell polynomial.

(Concerned with sequences \underline{A087426} and \underline{A093131}.)

Received October 6 2011; revised version received December 27 2011. Published in Journal of Integer Sequences, December 27 2011.

Return to Journal of Integer Sequences home page.