generalizations of some identities

involving the fibonacci numbers

March 7, 2003

Toufik Mansour ^{1}

Department of Mathematics, Chalmers University of Technology, S-412 96 Göteborg,

Sweden

                        toufik@math.chalmers.se

1 Introduction

The generalized Fibonacci and Lucas numbers are defined by

U_{n}(p, q) = \frac{α^{n} − β^{n}}{α − β} , V_{n}(p, q) = α^{n} + β^{n},  (1)

where α = \frac{1}{2}(p + \sqrt{p^{2} − 4q}) and β = \frac{1}{2}(p − \sqrt{p^{2} − 4q}). Clearly, U_{n}(p, q) and V_{n}(p, q) are the usual Fibonacci and Lucas sequences {F_{n}} and {L_{n}} when p = 1 and q = −1.

1Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

Definition 1.1 Let d ≥ 0. For any n ≥ 0, we define

s_{d}(n; p, q; k) = ∑_{j_{1}+j_{2}+···+j_{d}=n} ∏_{i=1}^{d} U_{k·j_{i}}(p, q).

For the Fibonacci numbers, Zhang [3] found the following identities:

s_{2}(n; 1, −1; 1) = \frac{1}{5}((n − 1)F_{n} + 2nF_{n−1}), n ≥ 1,  (2)
s_{3}(n; 1, −1; 1) = \frac{1}{50}((5n^{2} − 9n − 2)F_{n−1} + (5n^{2} − 3n − 2)F_{n−2}), n ≥ 2, (3)

and when n ≥ 3,

s_{4}(n; 1, −1; 1) = \frac{1}{150}((4n^{3} − 12n^{2} − 4n + 12)F_{n−2} + (3n^{3} − 6n^{2} − 3n + 6)F_{n−3}). (4)

Recently, Zhao and Wang [2] extended these identites to the case of {U_{n}(p, q)} and {V_{n}(p, q)}; for n ≥ 1

s_{2}(n; p, q; k) = \frac{U_{k}(p, q)}{V_{k}^{2}(p, q) − 4q^{k}} ((n − 1)U_{nk}(p, q)V_{k}(p, q) − 2nq^{k}U_{(n−1)k}(p, q)), (5)

for n ≥ 2,

\begin{aligned}s_{3}(n; p, q; k) & = \frac{U_{k}^{2}(p,q)}{2(V_{k}^{2}(p,q)−4q^{k})^{2}} ((n − 1)(n − 2)V_{k}^{2}(p, q)U_{nk}(p, q) \\ & −q^{k}V_{k}(p, q)(4n^{2} − 6n − 4)U_{(n−1)k}(p, q) \\ & +(4n^{2} − 28n + 28(n − 3)V_{k}(p, q) + 80)U_{(n−2)k}(p, q)), \end{aligned}  (6)

and when n ≥ 3,

\begin{aligned}s_{4}(n; p, q; k) & = \frac{U_{k}^{3}(p,q)}{6(V_{k}^{2}(p,q)−4q^{k})^{3}} (V_{k}^{3}(p, q)(n − 1)(n − 2)(n − 3)U_{nk}(p, q) \\ & −6q^{k}V_{k}^{2}(p, q)(n − 2)(n − 3)(n + 1)U_{(n−1)k}(p, q) \\ & +12q^{2k}V_{k}(p, q)(n − 3)(n^{2} + n − 1)U_{(n−2)k}(p, q) \\ & −8q^{3k}n(n^{2} − 4)U_{(n−3)k}(p, q)). \end{aligned}  (7)

In this paper, we extend the above conclusions. We establish an identity for the case s_{d}(n; p, q; k) for any d ≥ 2.

2 Main results

We denote by G_{k}(x; p, q) the generating function of {U_{n·k}(p, q)}, that is, G_{k}(x; p, q) = ∑_{n≥0} U_{n·k}(p, q)x^{n}, where k is a positive integer. Clearly, by Definition 1 and the geometric formula,

G_{k}(x; p, q) = \frac{xU_{k}(p, q)}{1 − V_{k}(p, q)x + q^{k}x^{2}} .

We define F_{k}(x) = F_{k}(x; p, q) = \frac{G_{k}(x;p,q)}{x}. Then

F_{k}(x) = ∑_{n≥1} U_{n·k}(p, q)x^{n−1} = \frac{U_{k}(p, q)}{1 − V_{k}(p, q)x + q^{k}x^{2}} .  (8)

Definition 2.1 Let a(0, d) = 4^{d} for any d ≥ 0, and a(ℓ, 0) = 0 for any ℓ ≥ 1. We define a(ℓ, d) for ℓ, d ≥ 1 by a(ℓ, d) = 4(ℓ + 1) · a(ℓ, d − 1) + ℓ · a(ℓ − 1, d − 1).

Using this definition we quickly generate the numbers a(ℓ, d); the first few of these numbers are given in Table 1.

\begin{matrix}d\ℓ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 16 & 12 & 2 & 0 & 0 & 0 & 0 \\ 3 & 64 & 112 & 48 & 6 & 0 & 0 & 0 \\ 4 & 256 & 960 & 800 & 240 & 24 & 0 & 0 \\ 5 & 1024 & 7936 & 11520 & 6240 & 1440 & 120 & 0 \\ 6 & 4096 & 64512 & 154112 & 134400 & 53760 & 10080 & 720 \end{matrix}

Table 1: Values of a(ℓ, d) where 0 ≤ ℓ, d ≤ 6.

We can also use Definition 2.1 to find an explicit formula for a(ℓ, d).

Lemma 2.2 For any ℓ, d ≥ 0,

a(ℓ, d) = 4^{d−ℓ} ∑_{j=0}^{ℓ}(−1)^{j}\binom{ℓ}{j}(ℓ + 1 − j)^{d}.

Proof. By Definition 2.1 it is easy to see that the lemma holds for ℓ = 0 or d = 0. Using induction on d and ℓ we get that

4(ℓ + 1) · a(ℓ, d − 1) + ℓ · a(ℓ − 1, d − 1)

= (ℓ + 1)4^{d−ℓ} ∑_{j=0}^{d}(−1)^{j}\binom{ℓ}{j}(ℓ + 1 − j)^{d−1} + ℓ · 4^{d−ℓ} ∑_{j=0}^{ℓ−1}(−1)^{j}\binom{ℓ−1}{j}(ℓ − j)^{d−1}

= 4^{d−ℓ} [(ℓ + 1) ∑_{j=0}^{ℓ}(−1)^{j}\binom{ℓ}{j}(ℓ + 1 − j)^{d−1} + ℓ ∑_{j=1}^{ℓ}(−1)^{j−1}\binom{ℓ−1}{j−1}(ℓ + 1 − j)^{d−1}]

= 4^{d−ℓ} [(ℓ + 1)^{d} + ∑_{j=1}^{ℓ}(−1)^{j}\binom{ℓ}{j}(ℓ + 1 − j)^{d}] = a(ℓ, d + 1),

as requested. □

Definition 2.3 Let b(1, d) = (−2)^{d−1} for any d ≥ 1, and b(ℓ, 1) = 0 for any ℓ ≥ 2. We define b(ℓ, d) for ℓ, d ≥ 2 by b(ℓ, d) = b(ℓ − 1, d − 1) − 2ℓ · b(ℓ, d − 1).

Using this definition we quickly generate the numbers b(ℓ, d); the first few of these numbers are given in Table 2.

\begin{matrix}d\ℓ & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & −2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 4 & −6 & 1 & 0 & 0 & 0 & 0 \\ 4 & −8 & 28 & −12 & 1 & 0 & 0 & 0 \\ 5 & 16 & −120 & 100 & −20 & 1 & 0 & 0 \\ 6 & −32 & 496 & −720 & 260 & −30 & 1 & 0 \end{matrix}

Table 2: Values of b(ℓ, d) where 0 ≤ ℓ, d ≤ 6.

We can also use Definition 2.3 to find an explicit formula for the numbers b(ℓ, d).

Lemma 2.4 For any ℓ, d ≥ 1,

b(ℓ, d) = \frac{(−1)^{d−1}2^{d−ℓ}}{(ℓ − 1)!} ∑_{j=0}^{ℓ−1}(−1)^{j}\binom{ℓ − 1}{j}(j + 1)^{d−1}.

Proof. By Definition 2.3 it is easy to see that the lemma holds for ℓ = 1 or d = 1. Using induction on d and ℓ we get that

b(ℓ − 1, d − 1) − 2ℓ · b(ℓ, d − 1)

= \frac{(−1)^{d−2}2^{d−ℓ}}{(ℓ−2)!} ∑_{j=0}^{ℓ−2}(−1)^{j}\binom{ℓ−2}{j}(j + 1)^{d−2} − \frac{2ℓ(−1)^{d−2}2^{d−ℓ−1}}{(ℓ−1)!} ∑_{j=0}^{ℓ−1}(−1)^{j}\binom{ℓ−1}{j}(j + 1)^{d−2}

= \frac{(−1)^{d−1}2^{d−ℓ}}{(ℓ−1)!} [ℓ ∑_{j=0}^{ℓ−1}(−1)^{j}\binom{ℓ−1}{j}(j + 1)^{d−2} − (ℓ − 1) ∑_{j=0}^{ℓ−2}(−1)^{j}\binom{ℓ−2}{j}(j + 1)^{d−2}]

= \frac{(−1)^{d−1}2^{d−ℓ}}{(ℓ−1)!} [(−1)^{d−1}ℓ^{d−1} + ∑_{j=0}^{ℓ−2}(−1)^{j} (ℓ\binom{ℓ−1}{j} − (ℓ − 1)\binom{ℓ−2}{j}) (j + 1)^{d−2}]

= \frac{(−1)^{d−1}2^{d−ℓ}}{(ℓ−1)!} [(−1)^{d−1}ℓ^{d−1} + ∑_{j=0}^{ℓ−2}(−1)^{j}\binom{ℓ−1}{j}(j + 1)^{d−1}]

= \frac{(−1)^{d−1}2^{d−ℓ}}{(ℓ−1)!} ∑_{j=0}^{ℓ−1}(−1)^{j}\binom{ℓ−1}{j}(j + 1)^{d−1} = b(ℓ, d),

as requested. □

Now we introduce a relation that plays the crucial role in the proof of the main result of this paper.

Proposition 2.5 Let d ≥ 1. The generating function F_{k}(x; p, q) satisfies the following equation:

\begin{aligned}∑_{j=0}^{d} & [(4q^{k})^{d−j} (∑_{i=0}^{j}(−1)^{i}\binom{j}{i}(j + 1 − i)^{d}) (\frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} )^{j} F_{k}^{j+1}(x; p, q)] \\ & = ∑_{j=1}^{d} [\frac{(−1)^{d−1}(2q^{k})^{d−j}}{(j−1)!} (∑_{i=0}^{j−1}(−1)^{i}\binom{j−1}{i}(i + 1)^{d−1}) (V_{k}(p, q) − 2q^{k}x)^{j} F_{k}^{(j)}(x; p, q)] , \end{aligned}

where F_{k}^{(j)}(x; p, q) is the jth derivative with respect to x of F_{k}(x; p, q). Proof. We define A = \frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} and B = V_{k}(p, q) − 2q^{k}x. Let us prove this theorem by induction on d. Noticing that

F_{k}^{(1)}(x; p, q) = \frac{(V_{k}(p, q) − 2q^{k}x)F_{k}(x; p, q)}{1 − V_{k}(p, q)x + q^{k}x^{2}},  (9)

we get

4q^{k}F_{k}(x; p, q) + A · F_{k}^{2}(x; p, q) = B · F_{k}^{(1)}(x; p, q),

therefore, the theorem holds for d = 1. Now we suppose that the theorem holds for d, that is,

\begin{matrix}∑_{j=0}^{d} a(j, d)q^{(d−j)k} (\frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} )^{j} F_{k}^{j+1}(x; p, q) \\ = ∑_{j=1}^{d} b(j, d)q^{(d−j)k} (V_{k}(p, q) − 2q^{k}x)^{j} F_{k}^{(j)}(x; p, q). \end{matrix}

Therefore, derivative this equation with respect to x we have that

\begin{matrix}∑_{j=0}^{d}(j + 1)a(j, d)q^{(d−j)k}A^{j}F_{k}^{j}(x; p, q)F_{k}^{(1)}(x; p, q) \\ = ∑_{j=1}^{d} b(j, d)q^{(d−j)k}B^{j}F_{k}^{(j+1)}(x; p, q) − ∑_{j=1}^{d} 2jq^{k}b(j, d)q^{(d−j)k}B^{j−1}F_{k}^{(j)}(x; p, q). \end{matrix}

If multiplying by B and using Equation 9 then we get that

\begin{matrix}∑_{j=0}^{d}(j + 1)a(j, d)q^{(d−j)k}A^{j+1}F_{k}^{j+2}(x; p, q) + ∑_{j=0}^{d} 4(j + 1)a(j, d)q^{(d+1−j)k}A^{j}F_{k}^{j+1}(x; p, q) \\ = ∑_{j=2}^{d+1} b(j − 1, d)q^{(d+1−j)k}B^{j}F_{k}^{(j)}(x; p, q) − ∑_{j=1}^{d} 2jb(j, d)q^{(d+1−j)k}B^{j}F_{k}^{(j)}(x; p, q), \end{matrix}

equivalently,

\begin{matrix}∑_{j=0}^{d+1}(ja(j − 1, d) + 4(j + 1)a(j, d))q^{(d+1−j)k}A^{j}F_{k}^{j+1}(x; p, q) \\ = ∑_{j=1}^{d+1}(b(j − 1, d) − 2jb(j, d))q^{(d+1−j)k}B^{j}F_{k}^{(j)}(x; p, q), \end{matrix}

Therefore, using Definition 2.1 and Definition 2.3 we have that

∑_{j=0}^{d+1} a(j, d + 1)q^{(d+1−j)k}A^{j}F_{k}^{j+1}(x; p, q) = ∑_{j=1}^{d+1} b(j, d + 1)q^{(d+1−j)k}B^{j}F_{k}^{(j)}(x; p, q).

Hence, using Lemma 2.2 and Lemma 2.4 we get the desired result. □

By the above proposition, we have the main result of this paper.

Theorem 2.6 Let d ≥ 1. For any n ≥ d,

\begin{matrix}∑_{j=0}^{d} & [(4q^{k})^{d−j} (∑_{i=0}^{j}(−1)^{i}\binom{j}{i}(j + 1 − i)^{d}) (\frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} )^{j} s_{j+1}(n + j − d; p, q; k)] \\ = ∑_{j=1}^{d} [\frac{(−1)^{d−1}(2q^{k})^{d−j}}{(j−1)!} (∑_{i=0}^{j−1}(−1)^{i}\binom{j−1}{i}(i + 1)^{d−1}) (∑_{s=0}^{j} v_{d,j,s}(n)U_{(n+j−d−s)k}(p, q)\binom{j}{s})] , \end{matrix}

where v_{d,j,s}(n) = (−2q^{k})^{s}V_{k}^{j−s}(p, q) ∏_{i=1}^{j}(n + j − d − s − i).

Proof. If comparing the coefficients of x^{n−(d+1)} on both sides of Proposition 2.5 we get the desired result. □

Theorem 2.6 provides a finite algorithm for finding s_{d}(n; p, q; k) in terms of U_{nk}(p, q) and V_{nk}(p, q), since we have to consider all s_{j}(n; p, q; k) for j = 1, 2, …, d. The algorithm has been implemented in Maple, and yields explicit results for 1 ≤ d ≤ 6. Below we present several explicit calculations.

Corollary 2.7 (see Zhao and Wang [2, Equation 9]) For any n ≥ 1,

s_{2}(n; p, q; k) = \frac{U_{k}(p, q)}{V_{k}^{2}(p, q) − 4q^{k}} ((n − 1)V_{k}(p, q)U_{nk}(p, q) − 2nq^{k}U_{(n−1)k}(p, q)).

Proof. Theorem 2.6 for d = 2 yields

\begin{matrix}4q^{k}s_{1}(n − 1; p, q; k) + \frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} s_{2}(n; p, q; k) \\ = (n − 1)V_{k}(p, q)U_{nk}(p, q) − 2(n − 2)q^{k}U_{(n−1)k}(p, q). \end{matrix}

Using the fact that s_{1}(n; p, q; k) = U_{nk}(p, q) we get the desired result. □ Corollary 2.8 (see Zhao and Wang [2, Equation 10]) For any n ≥ 2,

s_{3}(n; p, q; k) = \frac{U_{k}^{2}(p,q)}{2(V_{k}^{2}(p,q)−4q^{k})^{2}} ((n − 1)(n − 2)V_{k}^{2}(p, q)U_{nk}(p, q)
−2q^{k}(n − 2)(2n + 1)V_{k}(p, q)U_{(n−1)k}(p, q)
+4q^{2k}(n − 2)(n + 2)U_{(n−2)k}(p, q)).

Proof. Theorem 2.6 for d = 3 yields

16q^{2k}s_{1}(n − 2; p, q; k) + 12q^{k} \frac{V_{k}^{2}(p,q)−4q^{k}}{U_{k}(p,q)} s_{2}(n − 1; p, q; k) + \frac{2(V_{k}^{2}(p,q)−4q^{k})^{2}}{U_{k}^{2}(p,q)} s_{3}(n; p, q; k) = (n − 1)(n − 2)V_{k}^{2}(p, q)U_{nk}(p, q) − 2(n − 2)(2n − 5)q^{k}V_{k}(p, q)U_{(n−1)k}(p, q)

+4q^{2k}(n − 3)^{2}U_{(n−2)k}(p, q).

Using Corollary 2.7 with the fact that s_{1}(n; p, q; k) = U_{nk}(p, q) we get the desired result. □ Similarly, if applying Theorem 2.6 for d with using the formulas of s_{j}(n; p, q; k) for j = 1, 2, …, d − 1, then we get the following result (in the case d = 4 see [2, Equation 11]).

Corollary 2.9 We have

(i) For any n ≥ 3,

s_{4}(n; p, q; k)
= \frac{U_{k}^{3}(p,q)}{6(V_{k}^{2}(p,q)−4q^{k})^{3}} (V_{k}^{3}(p, q)(n − 1)(n − 2)(n − 3)U_{nk}(p, q)
−6q^{k}V_{k}^{2}(p, q)(n − 2)(n − 3)(n + 1)U_{(n−1)k}(p, q)
+12q^{2k}V_{k}(p, q)(n − 3)(n^{2} + n − 1)U_{(n−2)k}(p, q)
−8q^{3k}n(n^{2} − 4)U_{(n−3)k}(p, q)).

(ii) For any n ≥ 4,

s_{5}(n; p, q; k)
= \frac{U_{k}^{4}(p,q)}{4!(V_{k}^{2}(p,q)−4q^{k})^{4}} (V_{k}^{4}(p, q)(n − 1)(n − 2)(n − 3)(n − 4)U_{nk}(p, q)
−4q^{k}V_{k}^{3}(p, q)(n − 2)(n − 3)(n − 4)(2n + 3)U_{(n−1)k}(p, q)
+12q^{2k}V_{k}^{2}(p, q)(n − 3)(n − 4)(2n^{2} + 4n − 1)U_{(n−2)k}(p, q)
−8q^{3k}V_{k}(p, q)(n − 4)(2n + 1)(2n^{2} + 2n − 9)U_{(n−3)k}(p, q)
+16q^{4k}(n − 3)(n − 1)(n + 1)(n + 3)U_{(n−4)k}(p, q)).

(iii) For any n ≥ 5,

s_{6}(n; p, q; k) = \frac{U_{k}^{5}(p,q)}{5!(V_{k}^{2}(p,q)−4q^{k})^{5}} (V_{k}^{5}(p, q)(n − 1)(n − 2)(n − 3)(n − 4)(n − 5)U_{nk}(p, q) −10q^{k}V_{k}^{4}(p, q)(n − 2)(n − 3)(n − 4)(n − 5)(n + 2)U_{(n−1)k}(p, q) +20q^{2k}V_{k}^{3}(p, q)(n − 3)(n − 4)(n − 5)(2n^{2} + 6n + 1)U_{(n−2)k}(p, q) −40q^{3k}V_{k}^{2}(p, q)(n − 4)(n − 5)(n + 1)(2n^{2} + 4n − 9)U_{(n−3)k}(p, q) +80q^{4k}V_{k}(p, q)(n − 5)(n^{4} + 2n^{3} − 10n^{2} − 11n + 9)U_{(n−4)k}(p, q) −32q^{5k}n(n − 4)(n − 2)(n + 2)(n + 4)U_{(n−5)k}(p, q)).

From these results, it is very easy to obtain Equations 2-4. If k = 1 and p = −q = 1, then by using Corollary 2.9 together with the recurrence F_{n} = F_{n−1} + F_{n−2} we arrive to

\begin{matrix}∑_{a+b+c+d+e=n} F_{a}F_{b}F_{c}F_{d}F_{e} \\ = \frac{1}{4!·5^{4}} (3(n − 1)(8n^{3} − 5n^{2} − 27n + 50)F_{n} − 20n(5n^{2} − 17)F_{n−1}) \end{matrix}

\begin{matrix}∑_{a+b+c+d+e+f=n} F_{a}F_{b}F_{c}F_{d}F_{e}F_{f} \\ = \frac{1}{5!·5^{4}} ((n − 1)(5n^{4} − 70n^{3} − 65n^{2} + 490n + 264)F_{n} + 2n(5n^{4} + 5n^{2} − 226)F_{n−1}). \end{matrix}

References

[1] A.F. Horadam and Bro. J. M. Mahon, Pell and Pell-Lucas polynomials, The Fibonacci Quartely 23 (1985) 7–20.

[2] F. Zhao and T. Wang, Generalizations of some identities involving the Fibonacci numbers, The Fibonacci Quarterly 39 (2001) 165–167.

[3] W. Zhang, Some identities involving Fibonacci numbers, The Fibonacci Quarterly 35 (1997) 225–229.

2000 Mathematics Subject Classification: Primary 11B39, 11B83; Secondary 05A15