Several Generating Functions for Second-Order Recurrence Sequences

István Mező Institute of Mathematics University of Debrecen Hungary

                      imezo@math.klte.hu

Abstract Carlitz and Riordan began a study on closed form of generating functions for powers of second-order recurrence sequences. This investigation was completed by Stănică. In this paper we consider exponential and other types of generating functions for such sequences. Moreover, an extensive table of generating functions is provided.

1 Introduction

The Fibonacci sequence, which is is sequence \underline{A000045} in Sloane’s Encylopedia, [11] is defined recursively as follows:

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

with initial conditions

F_{0} = 0, F_{1} = 1.

The Lucas numbers L_{n}, which comprise Sloane’s sequence \underline{A000032}, are defined by the same manner but with initial conditions

L_{0} = 2, L_{1} = 1.

In 1962, Riordan [9] determined the generating functions for powers of Fibonacci numbers:

f_{k}(x) = ∑_{n=0}^{∞} F_{n}^{k}x^{n}.

This question had been suggested by Golomb [4] in 1957. Riordan found the recursive solution

(1 − L_{k}x + (−1)^{k}x^{2})f_{k}(x) = 1 + x ∑_{j=1}^{[k/2]}(−1)^{j}A_{kj}f_{k−2j}(x(−1)^{j}),  (1)

with initial functions

f_{0}(x) = \frac{1}{1 − x}, and f_{1}(x) = \frac{1}{1 − x − x^{2}} .

We mention that in his paper Riordan used the F_{0} = F_{1} = 1 condition. In the result above, the coefficients A_{kj} have a complicated definition and cannot be handled easily.

In the same journal and volume, Carlitz [3] made the following generalization. Let

u_{n} = pu_{n−1} − qu_{n−2} (n ≥ 2),

with initial conditions

u_{0} = 1, u_{1} = p.

He computed the generating functions for the sequences u_{n}^{k}. They have the same form as Eq. (1).

In his recent paper [12], Stănică gave the most general and simple answer for the questions above (see Theorem 1) with an easy proof. Namely, let the so-called second-order recurrence sequence be given by

u_{n} = pu_{n−1} + qu_{n−2} (n ≥ 2),  (2)

where p, q, u_{0} and u_{1} are arbitrary numbers such that we eliminate the degenerate case p^{2} + 4q = 0. Then let

α = \frac{1}{2}(p + \sqrt{p^{2} + 4q}), β = \frac{1}{2}(p − \sqrt{p^{2} + 4q}),  (3)

A = \frac{u_{1} − u_{0}β}{α − β} , B = \frac{u_{1} − u_{0}α}{α − β}.  (4)

It is known that u_{n} can be written in the form

u_{n} = Aα^{n} − Bβ^{n} (Binet formula).

Many famous sequences have this shape. A comprehensive table can be found at the end of the paper.

To present Stănică’s result, we need to introduce the sequence V_{n} given by its Binet formula:

V_{n} = α^{n} + β^{n}, V_{0} = 2, V_{1} = p.

Theorem 1 (Stănică). The generating function for the rth power of the sequence u_{n} is

∑_{n=0}^{∞} u_{n}^{r}x^{n} =

∑_{k=0}^{\frac{r−1}{2}}(−1)^{k}A^{k}B^{k}\binom{r}{k}\frac{A^{r−2k} − B^{r−2k} + (−b)^{k}(B^{r−2k}α^{r−2k} − A^{r−2k}β^{r−2k})x}{1 − (−b)^{k}V_{r−2k} − x^{2}},

if r is odd, and

∑_{n=0}^{∞} u_{n}^{r}x^{n} =

∑_{k=0}^{\frac{r}{2} −1}(−1)^{k}A^{k}B^{k}\binom{r}{k}\frac{B^{r−2k} + A^{r−2k} − (−b)^{k}(B^{r−2k}α^{r−2k} + A^{r−2k}β^{r−2k})x}{1 − (−b)^{k}V_{r−2k}x + x^{2}}

+\binom{r}{\frac{r}{2}} \frac{A^{\frac{r}{2}} (−B)^{\frac{r}{2}}}{1 − (−1)^{\frac{r}{2}} x},

if r is even.

In the spirit of this result we present the same formulas for even and odd indices, exponential generating functions for powers, product of such sequences and so on.

2 Non-exponential generating functions

The result in this and the following sections yield rich and varied examples which are collected in separate tables at the end of the paper.

First, the generating function for u_{n} is given:

Proposition 2. We have

∑_{n=0}^{∞} u_{n}x^{n} = \frac{u_{0} + (u_{1} − pu_{0})x}{1 − px − qx^{2}}.

For the sake of a more readable presentation, the proof of this statement and all of the others will be collected in a separate section. We remark that Proposition 2 is not new but the proof is easy and typical.

Sequences with even and odd indices appear so often that it is worth to construct the general generating function of this type.

Theorem 3. The generating function for the sequence u_{2n} is

∑_{n=0}^{∞} u_{2n}x^{n} = \frac{u_{0} + (u_{2} − u_{0}(p^{2} + 2q))x}{1 − (p^{2} + 2q)x + q^{2}x^{2}},

while

∑_{n=0}^{∞} u_{2n+1}x^{n} = \frac{u_{1} + (u_{0}pq − u_{1}q)x}{1 − (p^{2} + 2q)x + q^{2}x^{2}} .

Example 4. As a consequence, we can state the following identity which we use later.

∑_{n=0}^{∞} F_{2n}x^{n} = \frac{x}{1 − 3x + x^{2}} .

See the paper of Johnson [6], for example.

Generating functions for powers of even and odd indices are interesting. The following theorem contains these results. Theorem 5. Let u_{n} = pu_{n−1} + qu_{n−2} be a sequence with initial values u_{0} and u_{1}. Then

∑_{n=0}^{∞} u_{2n}^{r}x^{n} =

∑_{k=0}^{\frac{r−1}{2}}(−1)^{k}E^{k}F^{k}\binom{r}{k}\frac{E^{r−2k} − F^{r−2k} + q^{2k}(F^{r−2k}ρ^{r−2k} − E^{r−2k}σ^{r−2k})x}{1 − q^{2k}V_{r−2k} − x^{2}},

if r is odd, and

∑_{n=0}^{∞} u_{2n}^{r}x^{n} =

∑_{k=0}^{\frac{r}{2} −1}(−1)^{k}E^{k}F^{k}\binom{r}{k}\frac{F^{r−2k} + E^{r−2k} − q^{2k}(F^{r−2k}ρ^{r−2k} + E^{r−2k}σ^{r−2k})x}{1 − q^{2k}V_{r−2k}x + x^{2}}

+\binom{r}{\frac{r}{2}} \frac{E^{\frac{r}{2}} (−F)^{\frac{r}{2}}}{1 − (−1)^{\frac{r}{2}} x},

if r is even. For odd indices we have to make the substitution E ⇝ G and F ⇝ H. Here

ρ = \frac{1}{2} (p^{2} + 2q + p\sqrt{p^{2} + 4q}) ,
σ = \frac{1}{2} (p^{2} + 2q − p\sqrt{p^{2} + 4q}) ,
E = \frac{u_{2} − u_{0}σ}{ρ − σ} , F = \frac{u_{2} − u_{0}ρ}{ρ − σ},
G = \frac{u_{3} − u_{1}σ}{ρ − σ} , H = \frac{u_{3} − u_{1}ρ}{ρ − σ},
V_{n} = ρ^{n} + σ^{n}, V_{0} = 2, V_{1} = p^{2} + 2q.

Remark 6. These constants are calculated for the named sequences:

Sequence  ρ  σ  E F  G  H
F_{n}  \frac{3+\sqrt{5}}{2}  \frac{3−\sqrt{5}}{2}  \frac{\sqrt{5}}{5} \frac{\sqrt{5}}{5}  \frac{\sqrt{5}}{5}ϕ  \frac{\sqrt{5}}{5} \overline{ϕ}
L_{n}  \frac{3+\sqrt{5}}{2}  \frac{3−\sqrt{5}}{2}  1 −1 \frac{\sqrt{5}}{10}(5 + \sqrt{5}) \frac{\sqrt{5}}{10}(5 − \sqrt{5})
P_{n}  3 + 2\sqrt{2} 3 − 2\sqrt{2} \frac{\sqrt{2}}{4} \frac{\sqrt{2}}{4} \frac{\sqrt{2}}{4}(1 + \sqrt{2}) \frac{\sqrt{2}}{4}(1 − \sqrt{2})
Q_{n}  3 + 2\sqrt{2} 3 − 2\sqrt{2} 1 −1 \frac{\sqrt{2}}{2}(2 + \sqrt{2}) \frac{\sqrt{2}}{2}(2 − \sqrt{2})
J_{n}  4  1  \frac{1}{3}  \frac{1}{3}  \frac{2}{3}  \frac{−1}{3}
j_{n}  4  1  1 −1  2  1

The product of the sequences u_{n} and v_{n} has a simple generating function as given in the following proposition.

Proposition 7. Let u_{n} and v_{n} be two second-order recurrence sequences given by their Binet formulae:

u_{n} = Aα^{n} − Bβ^{n}, v_{n} = Cγ^{n} − Dδ^{n},

where A, B, C, D, α, β, γ, δ are defined as in Eqs. (3) and (4). Then the generating function for u_{n}v_{n} is

∑_{n=0}^{∞} u_{n}v_{n}x^{n} = \frac{AC}{1 − αγx} − \frac{AD}{1 − αδx} − \frac{BC}{1 − βγx} + \frac{BD}{1 − βδx}.

We mention that a similar statement can be obtained for the products u_{n}v_{2n}, u_{2n}v_{2n}, u_{2n+1}v_{2n}, u_{2n+1}v_{2n+1}, etc.

Remark 8. As a special case, let u_{n} = F_{n} and v_{n} = L_{n}. Then it is well known (from Binet formula, for example) that

A = B = \frac{1}{\sqrt{5}}, α = \frac{1 + \sqrt{5}}{2} β = \frac{1 − \sqrt{5}}{2},

C = 1, D = −1, γ = \frac{1 + \sqrt{5}}{2} δ = \frac{1 − \sqrt{5}}{2}.

The quantity \frac{1+\sqrt{5}}{2} is called the golden ratio (or golden mean, or golden section). For further use we apply the standard notation ϕ for this, and \overline{ϕ} for \frac{1−\sqrt{5}}{2}. We remark that ϕ\overline{ϕ} = −1 and ϕ − \overline{ϕ} = ϕ^{2} − \overline{ϕ}^{2} = \sqrt{5}.

Therefore

∑_{n=0}^{∞} F_{n}L_{n}x^{n} = \frac{1}{\sqrt{5}} (\frac{1}{1 − ϕ^{2}x} + \frac{1}{1 + x} − \frac{1}{1 + x} − \frac{1}{1 − \overline{ϕ}^{2}x})

= \frac{1}{\sqrt{5}} \frac{(ϕ^{2} − \overline{ϕ}^{2})x}{(1 − ϕ^{2}x)(1 − \overline{ϕ}^{2}x)} = \frac{x}{x^{2} − 3x + 1}.

Comparing the result obtained in Example 4, this yields the known identity

F_{2n} = F_{n}L_{n}.

See Mordell’s book [8, pp. 60–61].

Remark 9. The variation u_{n} = F_{n} and v_{n} = P_{n} (where P_{n} are the Pell numbers \underline{A000129}) also have combinatorial sense. See the paper of Sellers [10]. The generating function for F_{n}P_{n} is known \underline{A001582}, but it can be deduced using the proposition above:

∑_{n=0}^{∞} F_{n}P_{n}x^{n} = \frac{x − x^{3}}{x^{4} − 2x^{3} − 7x^{2} − 2x + 1}.

Using Theorem 15, the exponential generating function for F_{n}P_{n} is derived:

∑_{n=0}^{∞} F_{n}P_{n} \frac{x^{n}}{n!} = \frac{1}{4}\sqrt{\frac{2}{5}} [e^{ϕ(1+\sqrt{2})x} − e^{ϕ(1−\sqrt{2})x} − e^{\overline{ϕ}(1+\sqrt{2})x} + e^{\overline{ϕ}(1−\sqrt{2})x}] .

Remark 10. As the author realized, the sequence (J_{n}j_{n}) appears in the on-line encyclopedia [11] but not under this identification (J_{n} and j_{n} are called Jacobsthal \underline{A001045} and Jacobsthal-Lucas \underline{A014551} numbers). The sequence \underline{A002450} has the generating function as (J_{n}j_{n}). Thus, the definition of \underline{A002450} gives the (otherwise elementary but not depicted) observation

J_{n}j_{n} = \frac{4^{n} − 1}{3}.

Let us turn the discussion’s direction to the determination of generating functions with coefficients \frac{u_{n}}{n^{q}}. (We do not restrict ourselves to the case of positive q.) To do this, we present the notion of polylogarithms which are themselves generating functions, having coefficients \frac{1}{n^{q}}. Concretely,

Li_{q}(x) = ∑_{n=1}^{∞} \frac{x^{n}}{n^{q}} .

Because of the coefficients \frac{1}{n^{q}}, it is extremely difficult to find closed forms of these sums but the situation changes when we take negative powers:

∑_{n=1}^{∞} n^{q}x^{n} = Li_{−q}(x) = \frac{1}{(1 − x)^{q+1}} ∑_{i=0}^{q−1} \left⟨{q \atop i}\right⟩x^{q−i},

where the symbol \left⟨{a \atop b}\right⟩ denotes the Eulerian numbers; that is, \left⟨{a \atop b}\right⟩ is the number of permutations on the set 1, …, a in which exactly b elements are greater than the previous element [5].

After these introductory steps, we state the following.

Proposition 11. For any u_{n} second-order recurrence sequence and for any q ∈ ℤ,

∑_{n=1}^{∞} \frac{u_{n}}{n^{q}} x^{n} = A Li_{q}(αx) − B Li_{q}(βx).

In particular, if q = 1 then

∑_{n=1}^{∞} \frac{u_{n}}{n} x^{n} = −A ln(1 − αx) + B ln(1 − βx),  (5)

while for q = −1

∑_{n=1}^{∞} nu_{n}x^{n} = A\frac{x}{(1 − αx)^{2}} − B \frac{x}{(1 − βx)^{2}} .

Applications can be found at the end of the paper. We mention that the special case u_{n} = F_{n} and x = \frac{1}{2} was investigated by Benjamin et al. [2] from a probabilistic point of view. Moreover, we can easily formulate the parallel results for even and odd indices:

∑_{n=1}^{∞} \frac{u_{2n}}{n^{q}} x^{n} = E Li_{q}(ρx) − F Li_{q}(σx),

∑_{n=1}^{∞} \frac{u_{2n+1}}{n^{q}} x^{n} = G Li_{q}(ρx) − H Li_{q}(σx).

Remark 12. In their paper on transcendence theory, Adhikari et al. [1] noted the beautiful fact that the sum

∑_{n=1}^{∞} \frac{F_{n}}{n2^{n}}

is transcendental.

Possessing the results above, we are able to take a closer look at this sum. Let u_{n} = F_{n} and x = \frac{1}{2} in Eq. (5). Then

∑_{n=1}^{∞} \frac{F_{n}}{n2^{n}} = −\frac{1}{\sqrt{5}} ln (1 − \frac{ϕ}{2}) + \frac{1}{\sqrt{5}} ln (1 − \frac{\overline{ϕ}}{2})

= \frac{1}{\sqrt{5}} (− ln (\frac{3 − \sqrt{5}}{4}) + ln (\frac{3 + \sqrt{5}}{4})) = \frac{1}{\sqrt{5}} ln (\frac{3 + \sqrt{5}}{3 − \sqrt{5}})

= \frac{1}{\sqrt{5}} ln (\frac{2 − \overline{ϕ}}{2 − ϕ}) .

So, this value is a transcendental number.

A similar calculation shows that

∑_{n=1}^{∞} \frac{L_{n}}{n2^{n}} = 2 ln(2),

which is again a transcendental number. In addition, we present an interesting example for series whose members’ denominators and the sum are the same but the numerators are different. Namely,

∑_{n=1}^{∞} \frac{L_{n}}{n2^{n}} = 2 ln(2) = ∑_{n=1}^{∞} \frac{2}{n2^{n}} .

Finding closed form for different arguments of polylogarithms is an intensively investigated and very hard topic. Fortunately, some functional equations gives the chance to find a closed form for the sum of certain series involving Fibonacci and Lucas numbers. In the book [7, pp. 6–7, 137–139] of Lewin, these are all the known special values:

Li_{2}(1)  = \frac{π^{2}}{6} ,
Li_{2}(−1) = −\frac{π^{2}}{12} ,
Li_{2} (\frac{1}{2}) = \frac{π^{2}}{12} − \frac{1}{2} log^{2}(2),
Li_{2}(\overline{ϕ}) = \frac{1}{2} log^{2}(−\overline{ϕ}) − \frac{π^{2}}{15} ,
Li_{2}(−\overline{ϕ}) = − log^{2}(−\overline{ϕ}) + \frac{π^{2}}{10} ,
Li_{2}(−ϕ) = \frac{1}{2} log^{2}(ϕ) − \frac{π^{2}}{10} ,
Li_{2} (\frac{1}{ϕ^{2}} ) = \frac{π^{2}}{15} − \frac{1}{4} log^{2} (\frac{1}{ϕ^{2}} ),
Li_{3}(−1) = −\frac{3}{4}ζ(3),
Li_{3} (\frac{1}{2}) = \frac{7}{8}ζ(3) − \frac{π^{2}}{12} log(2) + \frac{1}{6} log^{3}(2),
Li_{3} (\frac{1}{ϕ^{2}} ) = \frac{4}{5}ζ(3) + \frac{π^{2}}{15} log (\frac{1}{ϕ^{2}} ) − \frac{1}{12} log^{3} (\frac{1}{ϕ^{2}} ).

Here ζ(3) = Li_{3}(1) is the Apéry’s constant without known closed form. With these identities, we deduce the following beautiful sums:

∑_{n=1}^{∞} \frac{(−1)^{n}F_{n}}{ϕ^{n}n^{2}} = \frac{1}{\sqrt{5}} (log^{2}(ϕ) − \frac{3π^{2}}{20} ) ,

∑_{n=1}^{∞} \frac{(−1)^{n}L_{n}}{ϕ^{n}n^{2}} = − log^{2}(ϕ) − \frac{π^{2}}{60},

∑_{n=1}^{∞} \frac{(−1)^{n}F_{n}}{ϕ^{n}n^{3}} = \frac{1}{\sqrt{5}} (\frac{2π^{2}}{15} log(ϕ) − \frac{2}{3} log^{3}(ϕ) − \frac{31}{20}ζ(3)) ,

∑_{n=1}^{∞} \frac{(−1)^{n}L_{n}}{ϕ^{n}n^{3}} = \frac{1}{20}ζ(3) − \frac{2π^{2}}{15} log(ϕ) + \frac{2}{3} log^{3}(ϕ).

Using Proposition 11,

∑_{n=1}^{∞} \frac{(−1)^{n}F_{n}}{ϕ^{n}n^{2}} = ∑_{n=1}^{∞} \frac{F_{n}}{n^{2}} \overline{ϕ}^{n} = \frac{1}{\sqrt{5}} Li_{2}(ϕ\overline{ϕ}) − \frac{1}{\sqrt{5}} Li_{2}(\overline{ϕ}\overline{ϕ})

= \frac{1}{\sqrt{5}} (Li_{2}(−1) − Li_{2} (\frac{1}{ϕ^{2}} )) ,

since \overline{ϕ} = \frac{−1}{ϕ}. Using the table of polylogarithms above, an elementary calculation shows the result. The same approach can be applied to derive the other sums (with data from the table with respect to A, B, α, β).

We can rewrite these sums in a more curious form, because

\frac{\sqrt{5} − 1}{2} = 2 sin (\frac{π}{10}) .

That is,

\frac{−1}{ϕ} = \overline{ϕ} = −2 sin (\frac{π}{10}) .

Whence, for example,

∑_{n=1}^{∞} \frac{(−1)^{n}F_{n}}{ϕ^{n}n^{2}} = ∑_{n=1}^{∞} \frac{(−2)^{n}F_{n}}{n^{2}} sin^{n} (\frac{π}{10}) .

3 Exponential generating functions

The results in the section above can also have exponential versions, which we give next. Since such expressions often cannot be simplified and finding the exponential generating function is only a substitution of constants, we omit the tables.

Theorem 13. The recurrence sequence u_{n} has the exponential generating function

∑_{n=0}^{∞} u_{n} \frac{x^{n}}{n!} = Ae^{αx} − Be^{βx},

while for even and odd indices

∑_{n=0}^{∞} u_{2n} \frac{x^{n}}{n!} = Ee^{ρx} − F e^{σx},

∑_{n=0}^{∞} u_{2n+1} \frac{x^{n}}{n!} = Ge^{ρx} − He^{σx},

where E, F, G, H, ρ, σ are defined in Theorem 5.

We phrase the exponential version of Stănică’s theorem in a wider sense.

Theorem 14. We have

∑_{n=0}^{∞} u_{n}^{r} \frac{x^{n}}{n!} = ∑_{k=0}^{r} \binom{r}{k}A^{k}(−B)^{r−k}e^{α^{k}β^{r−k}x},

∑_{n=0}^{∞} u_{2n}^{r} \frac{x^{n}}{n!} = ∑_{k=0}^{r} \binom{r}{k}E^{k}(−F)^{r−k}e^{ρ^{k}σ^{r−k}x},

∑_{n=0}^{∞} u_{2n+1}^{r} \frac{x^{n}}{n!} = ∑_{k=0}^{r} \binom{r}{k}G^{k}(−H)^{r−k}e^{ρ^{k}σ^{r−k}x}.

The exponential generating function for product of recurrence sequences is presented in the following

Theorem 15. Under the hypotheses of Proposition 7, we have

∑_{n=0}^{∞} u_{n}v_{n} \frac{x^{n}}{n!} = ACe^{αγx} − ADe^{αδx} − BCe^{βγx} + BDe^{βδx}.

Again, the same statement can be obtained for the products u_{n}v_{2n}, u_{2n}v_{2n}, u_{2n+1}v_{2n}, u_{2n+1}v_{2n+1}, etc.

4 Proofs

Proof of Proposition 2. Let the generating function be f(x). Then

f(x) − pxf(x) − qx^{2}f(x) = u_{0} + u_{1}x − pu_{0}x + ∑_{n=2}^{∞}(u_{n} − pu_{n−1} − qu_{n−2})x^{n}

= u_{0} + u_{1}x − pu_{0}x,

by Eq. (2). The result follows.

Proof of Theorem 3. In order to reach our aim, we need the following identity:

u_{2n} = (p^{2} + 2q)u_{2n−2} − q^{2}u_{2n−4}.  (6)

Since

u_{2n−1} = pu_{2n−2} + qu_{2n−3}, and u_{2n−2} = pu_{2n−3} + qu_{2n−4},

we get that

u_{2n−3} = \frac{1}{q}(u_{2n−1} − pu_{2n−2}) = \frac{1}{p}(u_{2n−2} − qu_{2n−4}).

If we express u_{2n−1} and consider the identity

u_{2n−1} = \frac{1}{p}(u_{2n} − qu_{2n−2}),

we will arrive at Eq. (6).

Let f_{e}(x) be the generating function for u_{2n} (“e” abbreviates the word “even”). Then

q^{2}x^{2}f_{e}(x) − (p^{2} + 2q)xf_{e}(x) + f_{e}(x)

= q^{2} ∑_{n=2}^{∞} u_{2n−4}x^{n} − (p^{2} + 2q) ∑_{n=1}^{∞} u_{2n−2}x^{n} + ∑_{n=0}^{∞} u_{2n}x^{n}

= ∑_{n=2}^{∞}(q^{2}u_{2n−4} − (p^{2} + 2q)u_{2n−2} + u_{2n})x^{n} − (p^{2} + 2q)u_{0}x + u_{0} + u_{2}x.

= u_{0} + (u_{2} − u_{0}(p^{2} + 2q))x.

We get the result.

Let f_{o}(x) be the generating function for the sequence u_{2n+1}.

pf_{o}(x) + qf_{e}(x) = ∑_{n=0}^{∞}(pu_{2n+1} + qu_{2n})x^{n} = ∑_{n=0}^{∞} u_{2n+2}x^{n}

= \frac{1}{x} ∑_{n=1}^{∞} u_{2n}x^{n} = \frac{1}{x} (∑_{n=0}^{∞} u_{2n}x^{n} − u_{0}) = \frac{1}{x}(f_{e}(x) − u_{0}).

Thus

f_{o}(x) = \frac{1}{p} (f_{e}(x) (\frac{1}{x} − q) − \frac{u_{0}}{x} ) .

If we consider the closed form of f_{e}(x) this formula can be transformed into the wanted form.

Proof of Theorem 5. We know (see Eq. (6)), that

u_{2n} = (p^{2} + 2q)u_{2n−2} − q^{2}u_{2n−4}.

This allows us to construct a second-order recurrence sequence v_{n} from u_{n} with the property

v_{n} = u_{2n},

namely,

v_{n} := (p^{2} + 2q)v_{n−1} − q^{2}v_{n−2}, v_{0} := u_{0}, v_{1} := u_{2}.  (7)

Therefore

ρ = \frac{1}{2} (p^{2} + 2q + \sqrt{(p^{2} + 2q)^{2} + 4(−q^{2})}) = \frac{1}{2} (p^{2} + 2q + p\sqrt{p^{2} + 4q}) ,

σ = \frac{1}{2} (p^{2} + 2q − \sqrt{(p^{2} + 2q)^{2} + 4(−q^{2})}) = \frac{1}{2} (p^{2} + 2q − p\sqrt{p^{2} + 4q}) ,

E = \frac{v_{1} − v_{0}σ}{ρ − σ} = \frac{u_{2} − u_{0}σ}{ρ − σ} , F = \frac{v_{1} − v_{0}ρ}{ρ − σ} = \frac{u_{2} − u_{0}ρ}{ρ − σ}

with respect to the sequence v_{n}. That is,

v_{n} = Eρ^{n} − F σ^{n}.

If we apply Stănică’s theorem for v_{n} = u_{2n}, we get the first statement. Secondly, we find the corresponding identity of Eq. (6).

u_{2n−1} = pu_{2n−2} + qu_{2n−3}, and u_{2n} = pu_{2n−1} + qu_{2n−2}.

We express u_{2n−2} from these:

u_{2n−2} = \frac{1}{p}(u_{2n−1} − qu_{2n−3}) = \frac{1}{q}(u_{2n} − pu_{2n−1}),

whence

u_{2n} = \frac{q}{p}(u_{2n−1} − qu_{2n−3}) + pu_{2n−1}.

On the other hand,

u_{2n} = \frac{1}{p}(u_{2n+1} − qu_{2n−1}).

Putting together the last two equalities we get the wanted formula:

u_{2n+1} = (p^{2} + 2q)u_{2n−1} − q^{2}u_{2n−3}.  (8)

Again, we are able to construct the sequence w_{n} for which

w_{n} = u_{2n+1}.

We are in the same situation as before. The only thing we should care about is that

w_{0} = u_{1}, w_{1} = u_{3}.

Proof of Proposition 7. If u_{n} and v_{n} have the form as in the proposition, then we see that

u_{n}v_{n} = AC(αγ)^{n} − AD(αδ)^{n} − BC(βγ)^{n} + BD(βδ)^{n}.

Thus

∑_{n=0}^{∞} u_{n}v_{n}x^{n}

= AC ∑_{n=0}^{∞}(αγx)^{n} − AD ∑_{n=0}^{∞}(αδx)^{n} − BC ∑_{n=0}^{∞}(βγx)^{n} + BD ∑_{n=0}^{∞}(βδx)^{n}.

The result follows. In addition, we mention that there are too many parameters, so it is not worth to look for an expression with parameters u_{0}, u_{1}, v_{0}, v_{1}, p, q, r, s directly. However, the remains can be completed easily, as the author calculated for the standard sequences.

Proof of Proposition 11. It is straightforward from Binet formula and the definition of polylogarithms.

Proof of Theorem 13. This proof is again straightforward,

∑_{n=0}^{∞} u_{n} \frac{x^{n}}{n!} = A ∑_{n=0}^{∞} \frac{(αx)^{n}}{n!} − B ∑_{n=0}^{∞} \frac{(βx)^{n}}{n!} = Ae^{αx} − Be^{βx}.

Finally, we choose v_{n} and w_{n} as in the proof of Theorem 5, and follow the usual argument.

Proofs of Theorems 14 and 15. The binomial theorem, the same approach as described in the proof of Theorem 5 and the Binet formula immediately gives the results:

∑_{n=0}^{∞} u_{n}^{r} \frac{x^{n}}{n!} = ∑_{n=0}^{∞}(Aα^{n} − Bβ^{n})^{r} \frac{x^{n}}{n!}

= ∑_{n=0}^{∞} ∑_{k=0}^{r} \binom{r}{k}A^{k}(α^{k})^{n}(−B)^{r−k}(β^{r−k})^{n} \frac{x^{n}}{n!}

= ∑_{k=0}^{r} \binom{r}{k}A^{k}(−B)^{r−k} ∑_{n=0}^{∞}(α^{k})^{n}(β^{r−k})^{n} \frac{x^{n}}{n!}

= ∑_{k=0}^{r} \binom{r}{k}A^{k}(−B)^{r−k}e^{α^{k}β^{r−k}x}.

The rest can be proven by the same approach.

5 Tables

Standard parameters for the named sequences

Name  Notation u_{0} u_{1} p q  First few values
Fibonacci  F_{n}  0 1 1 1 0, 1, 1, 2, 3, 5, 8, 13, 21
Lucas  L_{n}  2 1 1 1 2, 1, 3, 4, 7, 11, 18, 29, 47
Pell  P_{n}  0 1 2 1 0,1,2,5,12,29,70,169,408
Pell-Lucas  Q_{n}  2 2 2 1 2,2,6,14,34,82,198,478
Jacobsthal  J_{n}  0 1 1 2 0, 1, 1, 3, 5, 11, 21, 43, 85
Jacobsthal-Lucas  j_{n}  2 1 1 2 2,1,5,7,17,31,65,127,257
Sequence A B  α  β
F_{n}  \frac{1}{\sqrt{5}} \frac{1}{\sqrt{5}}  \frac{1+\sqrt{5}}{2}  \frac{1−\sqrt{5}}{2}
L_{n}  1 −1 \frac{1+\sqrt{5}}{2}  \frac{1−\sqrt{5}}{2}
P_{n}  \frac{\sqrt{2}}{4} \frac{\sqrt{2}}{4} 1 + \sqrt{2} 1 − \sqrt{2}
Q_{n}  1 −1 1 + \sqrt{2} 1 − \sqrt{2}
J_{n}  \frac{1}{3}  \frac{1}{3}  2  −1
j_{n}  1 −1  2  −1

Ordinary generating functions

Coefficient of x^{n} Generating function
F_{n}  \frac{x}{1−x−x^{2}}
L_{n}  \frac{2−x}{1−x−x^{2}}
P_{n}  \frac{x}{1−2x−x^{2}}
Q_{n}  \frac{2−2x}{1−2x−x^{2}}
J_{n}  \frac{x}{1−x−2x^{2}}
j_{n}  \frac{2−x}{1−x−2x^{2}}

Generating functions of even and odd indices

x^{n} Generating function x^{n} Generating function
F_{2n}  \frac{x}{1−3x+x^{2}}  F_{2n+1}  \frac{1−x}{1−3x+x^{2}}
L_{2n}  \frac{2−3x}{1−3x+x^{2}}  L_{2n+1}  \frac{1+x}{1−3x+x^{2}}
P_{2n}  \frac{2x}{1−6x+x^{2}}  P_{2n+1}  \frac{1−x}{1−6x+x^{2}}
Q_{2n}  \frac{2−6x}{1−6x+x^{2}}  Q_{2n+1}  \frac{2+2x}{1−6x+x^{2}}
J_{2n}  \frac{x}{1−5x+4x^{2}}  J_{2n+1}  \frac{1−2x}{1−5x+4x^{2}}
j_{2n}  \frac{2−5x}{1−5x+4x^{2}}  j_{2n+1}  \frac{1+2x}{1−5x+4x^{2}}

Generating functions for products of sequences

Coefficient of x^{n} Generating function
F_{n}L_{n}  \frac{x}{1−3x+x^{2}}
F_{n}P_{n}  \frac{x−x^{3}}{1−2x−7x^{2}−2x^{3}+x^{4}}
F_{n}Q_{n}  \frac{2x+2x^{2}+2x^{3}}{1−2x−7x^{2}−2x^{3}+x^{4}}
F_{n}J_{n}  \frac{1−2x^{2}}{1−x−7x^{2}−2x^{3}+4x^{4}}
F_{n}j_{n}  \frac{x+4x^{2}+2x^{3}}{1−x−7x^{2}−2x^{3}+4x^{4}}
L_{n}P_{n}  \frac{x+4x^{2}+x^{3}}{1−2x−7x^{2}−2x^{3}+x^{4}}
L_{n}Q_{n}  \frac{4−6x−14x^{2}−2x^{3}}{1−2x−7x^{2}−2x^{3}+x^{4}}
L_{n}J_{n}  \frac{x+2x^{2}+2x^{3}}{1−x−7x^{2}−2x^{3}+4x^{2}}
L_{n}j_{n}  \frac{4−3x−14x^{2}−2x^{3}}{1−x−7x^{2}−2x^{3}+4x^{4}}
P_{n}Q_{n}  \frac{2x}{1−6x+x^{2}}
P_{n}J_{n}  \frac{x−2x^{3}}{1−2x−13x^{2}−4x^{3}+4x^{4}}
P_{n}j_{n}  \frac{x+8x^{2}+2x^{3}}{1−2x−13x^{2}−4x^{3}+4x^{4}}
Q_{n}J_{n}  \frac{2x+2x^{2}+4x^{3}}{1−2x−13x^{2}−4x^{3}+4x^{4}}
Q_{n}j_{n}  \frac{4−6x−26x^{2}−4x^{3}}{1−2x−13x^{2}−4x^{3}+4x^{4}}
J_{n}j_{n}  \frac{x}{1−5x+4x^{2}}

Generating functions for squares

x^{n} Gen. function x^{n} Gen. function  x^{n} Gen. function
F_{n}^{2}  \frac{x−x^{2}}{1−2x−2x^{2}+x^{3}} F_{2n}^{2}  \frac{x+x^{2}}{1−8x+8x^{2}−x^{3}}  F_{2n+1}^{2}  \frac{1−4x+x^{2}}{1−8x+8x^{2}−x^{3}}
L_{n}^{2}  \frac{4−7x−x^{2}}{1−2x−2x^{2}+x^{3}} L_{2n}^{2}  \frac{4−23x+9x^{2}}{1−8x+8x^{2}−x^{3}}  L_{2n+1}^{2}  \frac{1+8x+x^{2}}{1−8x+8x^{2}−x^{3}}
P_{n}^{2}  \frac{x−x^{2}}{1−5x−5x^{2}+x^{3}} P_{2n}^{2}  \frac{4x+4x^{2}}{1−35x+35x^{2}−x^{3}} P_{2n+1}^{2}  \frac{1−10x+x^{2}}{1−35x+35x^{2}−x^{3}}
Q_{n}^{2}  \frac{4−16x−4x^{2}}{1−5x−5x^{2}+x^{3}} Q_{2n}^{2}  \frac{4−104x+36x^{2}}{1−35x+35x^{2}−x^{3}} Q_{2n+1}^{2}  \frac{4+56x+4x^{2}}{1−35x+35x^{2}−x^{3}}
J_{n}^{2}  \frac{x−2x^{2}}{1−3x−6x^{2}+8x^{3}} J_{2n}^{2} \frac{x+4x^{2}}{1−21x+84x^{2}−64x^{3}} J_{2n+1}^{2} \frac{1−12x+16x^{2}}{1−21x+84x^{2}−64x^{3}}
j_{n}^{2}  \frac{4−11x−2x^{2}}{1−3x−6x^{2}+8x^{3}} j_{2n}^{2} \frac{4−59x+100x^{2}}{1−21x+84x^{2}−64x^{3}} j_{2n+1}^{2} \frac{1+28x+16x^{2}}{1−21x+84x^{2}−64x^{3}}

Generating functions for sequences (n · u_{(2)n})

x^{n} Gen. function  x^{n}  Gen. function
nF_{n}  \frac{x+x^{3}}{1−2x−x^{2}+2x^{3}+x^{4}} nF_{2n}  \frac{x−x^{3}}{1−6x+11x^{2}−6x^{3}+x^{4}}
nL_{n}  \frac{x+4x^{2}−x^{3}}{1−2x−x^{2}+2x^{3}+x^{4}} nL_{2n}  \frac{3x−4x^{2}+3x^{3}}{1−6x+11x^{2}−6x^{3}+x^{4}}
nP_{n}  \frac{x+x^{3}}{1−4x+2x^{2}+4x^{3}+x^{4}} nP_{2n}  \frac{2x−2x^{3}}{1−12x+38x^{2}−12x^{3}+x^{4}}
nQ_{n} \frac{2x+4x^{2}−2x^{3}}{1−4x+2x^{2}+4x^{3}+x^{4}} nQ_{2n}  \frac{6x−4x^{2}+6x^{3}}{1−12x+38x^{2}−12x^{3}+x^{4}}
nJ_{n} \frac{x+2x^{3}}{1−2x−3x^{2}+4x^{3}+4x^{4}} nJ_{2n} \frac{x−4x^{3}}{1−10x+33x^{2}−40x^{3}+16x^{4}}
nj_{n} \frac{x+8x^{2}−2x^{3}}{1−2x−3x^{2}+4x^{3}+4x^{4}} nj_{2n} \frac{5x−16x^{2}+20x^{3}}{1−10x+33x^{2}−40x^{3}+16x^{4}}

Generating functions for sequences (n · u_{2n+1})

Coefficient of x^{n} Generating function
nF_{2n+1}  \frac{2x−2x^{2}+x^{3}}{1−6x+11x^{2}−6x^{3}+x^{4}}
nL_{2n+1}  \frac{4x−2x^{2}−x^{3}}{1−6x+11x^{2}−6x^{3}+x^{4}}
nP_{2n+1}  \frac{5x−2x^{2}+x^{3}}{1−12x+38x^{2}−12x^{3}+x^{4}}
nQ_{2n+1}  \frac{14x−4x^{2}−2x^{3}}{1−12x+38x^{2}−12x^{3}+x^{4}}
nJ_{2n+1}  \frac{3x−8x^{2}+8x^{3}}{1−10x+33x^{2}−40x^{3}+16x^{4}}
nj_{2n+1}  \frac{7x−8x^{2}−8x^{3}}{1−10x+33x^{2}−40x^{3}+16x^{4}}

References

[1] S. D. Adhikari, N. Saradha, T. N. Shorey and R. Tijdeman, Transcendental infinite sums, Indag. Math. J. 12 (1) (2001), 1–14.

[2] A. T. Benjamin, J. D. Neer, D. E. Otero, J. A. Sellers, A probabilistic view of certain weighted Fibonacci sums, Fib. Quart. 41 (4) (2003), 360–364.

[3] L. Carlitz, Generating functions for powers of certain sequences of numbers, Duke Math. J. 29 (1962), 521–537.

[4] S. Golomb, Problem 4270, Amer. Math. Monthly 64(1) (1957), p. 49.

[5] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison Wesley, 1993.

[6] R. C. Johnson, Matrix method for Fibonacci and related sequences, notes for undegrad-

    uates, 2006. Available online at http://www.dur.ac.uk/bob.johnson/fibonacci/.

[7] L. Lewin, Dilogarithms and Associated Functions, Macdonald, London, 1958.

[8] L. J. Mordell, Diophantine Equations, Academic Press, London and New York, 1969.

[9] J. Riordan, Generating functions for powers of Fibonacci numbers, Duke Math. J. 29 (1962), 5–12.

[10] J. A. Sellers, Domino tilings and products of Fibonacci and Pell Numbers, J. Integer Seq. 5 (1), (2002), Article 02.1.2.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at http://www.research.att.com/~njas/sequences/.

[12] P. Stănică, Generating functions, weighted and non-weighted sums for powers of secondorder recurrence sequences, Fib. Quart. 41(4) (2003), 321–333.

2000 Mathematics Subject Classification: Primary 11B39. Keywords: Recurrence sequences, Fibonacci sequence, Lucas sequence, Pell sequence, Pell-Lucas sequence, Jacobsthal sequence, Jacobsthal-Lucas sequence, generating function, exponential generating function.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, \underline{A001045}, \underline{A001582}, \underline{A002450}, and \underline{A014551}.)

Received July 17 2007; revised version received April 24 2009. Published in Journal of Integer Sequences, April 29 2009.

Return to Journal of Integer Sequences home page.