Generating Matrices for Weighted Sums of Second Order Linear Recurrences

Emrah Kiliç TOBB Economics and Technology University Mathematics Department 06560 Sogutozu, Ankara Turkey

                       ekilic@etu.edu.tr

Pantelimon Stănică Naval Postgraduate School Applied Mathematics Department Monterey, CA 93943 USA

                       pstanica@nps.edu

Abstract In this paper, we give fourth order recurrences and generating matrices for the weighted sums of second order recurrences. We derive by matrix methods some new explicit formulas and combinatorial representations, and some relationships between the permanents of certain superdiagonal matrices and these sums.

1 Introduction

Let A be an integer such that A^{2} + 4 ≠ 0. Define the second order linear recurrence {U_{n}} as follows: for n > 0, let

U_{n} = AU_{n−1} + U_{n−2}

where U_{0} = 0 and U_{1} = 1. We also let V_{n} be the companion sequence satisfying the same recurrence with initial conditions V_{0} = 2, V_{1} = A. For example, when A = 1, then U_{n} = F_{n} (the nth Fibonacci number). Also, when A = 2, then U_{n} = P_{n} (the nth Pell number).

Many authors have studied various sums of certain products of terms of second order recurrences. Recently, the first author gave a new generating matrix, recurrence relation and some identities for squares and double products of terms of a second order linear recurrence via its generating matrix [2]. Matrix methods are very useful tools in solving problems stemming from number theory.

Further, some authors have studied weighted sums of terms of certain recurrences. For example, the following sums can be found in [3]:

∑_{i=1}^{n} iF_{i} = nF_{n+2} − F_{n+3} + 2

∑_{i=1}^{n} (n − i + 1) F_{i} = F_{n+4} − n − 3

In this paper, we consider the following weighted sum of terms of {U_{n}} , for n, t > 0

B_{n,t} = ∑_{i=1}^{n} (n − i) U_{ti}  (1)

The first few initial terms of {B_{n,1}} are

0, 1, A + 2, A^{2} + 2A + 4, A^{3} + 2A^{2} + 5A + 6, A^{4} + 2A^{3} + 6A^{2} + 8A + 9, ....

For A = 1, the Fibonacci case, the first few terms of {B_{n,1}} are

1, 3, 7, 14, 26, 46, 79, 133, 221, …,

which is Sloane’s sequence \underline{A001924}.

We derive two fourth order recurrence relations and two generating matrices for the weighted sums sequence {B_{n,t}} . We obtain some new explicit formulas and combinatorial representations for the weighted sums by matrix methods, involving certain superdiagonal determinants and the weighted sums. Further the generating functions for the sum sequences {B_{n,t}} for both even and odd integers n are obtained.

2 Recurrence relations for the weighted sums

In this section, we derive two fourth order recurrence relations for the sequence {B_{n,t}} for both the even and odd subscripted terms.

Lemma 1. For even integers t = 2r, r > 0, the sequence {B_{n,t}} satisfies the recurrence

B_{n,t} = (V_{t} + 2) B_{n−1,t} − 2 (V_{t} + 1) B_{n−2,t} + (V_{t} + 2) B_{n−3,t} − B_{n−4,t}, n > 3,  (2)

where B_{0,t} = 0, B_{1,t} = 0, B_{2,t} = U_{t}, B_{3,t} = (2U_{t} + U_{2t}) /U_{t}. Furthermore, for odd integers t = 2r + 1, r ≥ 0, the sequence {B_{n,t}} satisfies the recurrence

B_{n,t} = (V_{t} + 2) B_{n−1,t} − 2V_{t}B_{n−2,t} + (V_{t} − 2) B_{n−3,t} + B_{n−4,t}, n > 3,  (3)

where B_{0,t} = 0, B_{1,t} = 0, B_{2,t} = U_{t}, B_{3,t} = (2U_{t} + U_{2t}) /U_{t}.

Proof. First, observe that B_{k,t} − B_{k−1,t} = ∑_{i=1}^{k−1} U_{ti}. Next, we write the right-hand side of

equation (2) in the following way

(V_{t} + 2)B_{n−1,t} − 2(V_{t} + 1)B_{n−2,t} + (V_{t} + 2)B_{n−3,t} − B_{n−4,t}
= V_{t}(B_{n−1,t} − 2B_{n−2,t} + B_{n−3,t}) + 2(B_{n−1,t} − B_{n−2,t} + B_{n−3,t} − B_{n−4,t}) + B_{n−4,t}
= V_{t}(∑_{i=1}^{n−2} U_{ti} − ∑_{i=1}^{n−3} U_{ti}) + 2 (∑_{i=1}^{n−2} U_{ti} + ∑_{i=1}^{n−4} U_{ti}) + B_{n−4,t}

= V_{t}U_{t(n−2)} + 4 ∑_{i=1}^{n−4} U_{ti} + 2U_{t(n−3)} + 2U_{t(n−2)} + ∑_{i=1}^{n−4}(n − 4 − i)U_{ti}

= V_{t}U_{t(n−2)} + 2U_{t(n−3)} + 2U_{t(n−2)} + ∑_{i=1}^{n−4}(n − i)U_{ti}
= V_{t}U_{t(n−2)} + 2U_{t(n−3)} + 2U_{t(n−2)} + B_{n,t} − 3U_{t(n−3)} − 2U_{t(n−2)} − U_{t(n−1)}
= V_{t}U_{t(n−2)} − U_{t(n−3)} − U_{t(n−1)} + B_{n,t} = B_{n,t},

since V_{t}U_{t(n−2)} = U_{t(n−1)} + (−1)^{t}U_{t(n−3)} = U_{t(n−1)} + U_{t(n−3)}, when t is even, and the proof of the first claim is complete.

The second claim for odd integers t follows similarly

(V_{t} + 2)B_{n−1,t} − 2V_{t}B_{n−2,t} + (V_{t} − 2)B_{n−3,t} + B_{n−4,t}
= V_{t}(B_{n−1,t} − 2B_{n−2,t} + B_{n−3,t}) + 2(B_{n−1,t} − B_{n−3,t}) + B_{n−4,t}
= V_{t}U_{t(n−2)} + 4 ∑_{i=1}^{n−4} U_{ti} + 2U_{t(n−2)} + ∑_{i=1}^{n−4}(n − 4 − i)U_{ti}

= V_{t}U_{t(n−2)} + 2U_{t(n−3)} + 2U_{t(n−2)} + ∑_{i=1}^{n−4}(n − i)U_{ti}
= V_{t}U_{t(n−2)} + U_{t(n−3)} − U_{t(n−1)} + B_{n,t} = B_{n,t},

where we used that V_{t}U_{t(n−2)} = U_{t(n−1)} + (−1)^{t}U_{t(n−3)} = U_{t(n−1)} − U_{t(n−3)}, if t odd.

The next corollary can be derived from a straightforward application of the previous lemma (or it can also be proved directly).

Corollary 1. For even t = 2r, r > 0,

∑_{n=0}^{∞} B_{n,t}x^{n} = \frac{U_{t}x^{2} − 4U_{t} (V_{t} + 1) x^{4}}{1 − (V_{t} + 2) x + 2 (V_{t} + 1) x^{2} − (V_{t} + 2) x^{3} + x^{4}} .

For odd integers t = 2r + 1, r ≥ 0,

∑_{n=0}^{∞} B_{n,t}x^{n} = \frac{U_{t}x^{2}}{1 − (V_{t} + 2) x + 2V_{t}x^{2} − (V_{t} − 2) x^{3} − x^{4}} .

In [1], the authors obtain an explicit formula for the nth power of general companion matrix. Let the k × k companion matrix be

A_{k} = [ \begin{matrix}c_{1} & c_{2} & c_{3} & … & c_{k−1} & c_{k} \\ 1 & 0 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 \\ 0 & 0 & 1 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & … & 1 & 0 \end{matrix} ] .  (4)

Theorem 1 ([1]). The (i, j) entry a_{ij}^{(n)} (c_{1}, …, c_{k}) in the matrix A_{k}^{n} (c_{1}, …, c_{k}) is given by the following formula:

a_{ij}^{(n)} (c_{1}, c_{2}, …, c_{k}) = ∑_{(t_{1},t_{2},...t_{k})} \frac{t_{j} + t_{j+1} + ⋯ + t_{k}}{t_{1} + t_{2} + ⋯ + t_{k}} × \binom{t_{1} + t_{2} + ⋯ + t_{k}}{t_{1}, t_{2}, …, t_{k}}c_{1}^{t_{1}} … c_{k}^{t_{k}} (5)

where the summation is over nonnegative integers satisfying t_{1} + 2t_{2} + ⋯ + kt_{k} = n − i + j, and the coefficients in (5) are defined to be 1 if n = i − j.

Applying the previous theorem in our case, we get the following consequence.

Corollary 2. For r > 0,

∑_{i=1}^{n} (n − i) U_{2ir}

= ∑_{(n_{1},n_{2},n_{3},n_{4})} \binom{n_{1} + n_{2} + n_{3} + n_{4}}{n_{1}, n_{2}, n_{3}, n_{4}} (−1)^{n_{2}+n_{4}} (V_{2r} + 2)^{n_{1}+n_{3}} (2V_{2r} + 2)^{n_{2}} ,

and, for r ≥ 0,

∑_{i=1}^{n} (n − i) U_{i(2r+1)}

= ∑_{(n_{1},n_{2},n_{3},n_{4})} \binom{n_{1} + n_{2} + n_{3} + n_{4}}{n_{1}, n_{2}, n_{3}, n_{4}} (V_{2r+1} + 2)^{n_{1}} (−2V_{2r+1})^{n_{2}} (V_{2r+1} − 2)^{n_{3}} ,

where the summations are over nonnegative integers satisfying n_{1} + 2n_{2} + 3n_{3} + 4n_{4} = n − 2.

Proof. In Theorem 1, if i = 3, j = 1, c_{1} = c_{3} = V_{2r} + 2, c_{2} = −2 (V_{2r} + 1) and c_{4} = −1, then the proof of the first claim follows immediately from (5).

Similarly, the proof of the second claim follows immediately from (5) if we take i = 3, j = 1, c_{1} = c_{3} = V_{2r} + 2, c_{2} = −2 (V_{2r} + 1) and c_{4} = −1 in Theorem 1.

Next we derive generating matrices for the even and odd subscripted weighted sums. For this purpose, we define two auxiliary sequences via the sequence {B_{n,t}}. First we consider the even subscripted weighted sums.

Define two sequences as shown: for n > 3 and even t such that t = 2r, r > 0

Q_{n,t} = (V_{t} + 2) B_{n−1,t} − B_{n−2,t}  (6)

and for n > 2

H_{n,t} = −2 (V_{t} + 1) B_{n,t} + Q_{n,t}  (7)

where Q_{3,t} = V_{t} + 2, Q_{2,t} = Q_{1,t} = 0, Q_{0,t} = 1 and H_{2,t} = −2 (V_{t} + 1) , H_{1,t} = 0, H_{0,t} = 1, H_{−1,t} = 0, respectively.

From Lemma 1, we write the vector recurrence: for even t such that t = 2r, r > 0

[ \begin{matrix}B_{n+1,t} \\ B_{n,t} \\ B_{n−1,t} \\ B_{n−2,t} \end{matrix} ] = [ \begin{matrix}V_{t} + 2 & −2 (V_{t} + 1) & V_{t} + 2 & −1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} ] [ \begin{matrix}B_{n,t} \\ B_{n−1,t} \\ B_{n−2,t} \\ B_{n−3,t} \end{matrix} ] .

By (6) and (7), we generalize the above vector recurrence relation to the matrix recurrence relation:

T_{n+1,t} = D_{t}T_{n−1,t} = ⋯ = D_{t}^{n−1}T_{1,t} = D_{t}^{n}  (8)

where

T_{n,t} = \frac{1}{B_{2,t}} [ \begin{matrix}B_{n+2,t} & H_{n+1,t} & Q_{n+2,t} & −B_{n+1,t} \\ B_{n+1,t} & H_{n,t} & Q_{n+1,t} & −B_{n,t} \\ B_{n,t} & H_{n−1,t} & Q_{n,t} & −B_{n−1,t} \\ B_{n−1,t} & H_{n−2,t} & Q_{n−1,t} & −B_{n−2,t} \end{matrix} ]  (9)

and

D_{t} = [ \begin{matrix}V_{2r} + 2 & −2 (V_{2r} + 1) & V_{2r} + 2 & −1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} ] (= T_{1,t}).

Since T_{n,t} = T_{n−1,t}T_{1,t} = T_{1,t}T_{n−1,t}, we have the following result.

Corollary 3. For n > 3 and r > 0, the sequences {H_{n,2r}} and {Q_{n,2r}} satisfy the following recurrence

x_{n} = (V_{2r} + 2) x_{n−1} − 2 (V_{2r} + 1) x_{n−2} + (V_{2r} + 2) x_{n−3} − x_{n−4},

where x_{n} is either Q_{n,2r} or H_{n−1,2r}.

By the Binet formula for {U_{n}}, it is easy to show that U_{kn} = V_{k}U_{k(n−1)} + (−1)^{k+1} U_{k(n−2)}, for integers n > 1, k > 0. Without effort we obtain

Corollary 4. For n, k > 0, U_{k} | U_{kn}.

Perhaps it is worth mentioning that B_{2,t} = U_{t} divides B_{n,t} for all n > 1.

Similar to the case of the even subscripted sums, we derive similar results for the odd subscripted sums. For odd t = 2r + 1, we define the sequences {Q_{n,t}} and {H_{n,t}}, as follows

Q_{n,t} = (V_{t} + 2) B_{n−1,t} + B_{n−2,t}, n > 3,  (10)

and

H_{n,t} = −2V_{t}B_{n,t} + Q_{n,t}, n > 2,  (11)

where Q_{3,t} = V_{t} + 2, Q_{2,t} = Q_{1,t} = 0, Q_{0,t} = 1 and H_{2,t} = −2V_{t}, H_{1,t} = 0, H_{0,t} = 1, H_{−1,t} = 0, respectively.

Combining Lemma 1, (10) and (11), for odd t = 2r + 1, we write

T_{n,t} = D_{t}^{n}  (12)

where T_{n,t} is as in (9) and

D_{t} = [ \begin{matrix}V_{2r+1} + 2 & −2V_{2r+1} & V_{2r+1} − 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} ] .

Since T_{n,t} = T_{n−1,t}T_{1,t} = T_{1,t}T_{n−1,t}, we have the following result.

Corollary 5. For n > 3 and r ≥ 0, the sequences {H_{n,2r+1}} and {Q_{n,2r+1}} satisfy the recurrence

x_{n} = (V_{2r+1} + 2) x_{n−1} − 2V_{2r+1}x_{n−2} + (V_{2r+1} − 2) x_{n−3} + x_{n−4}

where x_{n} is either Q_{n,2r+1} or H_{n−1,2r+1}.

Since the matrix D_{t} does not have linear independent eigenvectors for all t, we cannot diagonalize the matrix. In the next section, we are able to get explicit formulas for the even and odd subscripted weighted sums by using alternative linear algebra methods instead of diagonalization.

3 Explicit Formulas for the Weighted Sums B_{n,t} by Matrix Methods

In this section, we derive some new explicit formulas for the weighted sums B_{n,t} for both even and odd n. In order to obtain explicit formulas, we use triangulization instead of diagonalization. After computing the nth power of a triangular matrix, we can show that our generating matrices are similar to certain triangular matrices via an invertible Vandermondelike matrix.

Now, we reconsider the matrix D_{t} for both odd and even t. After simple computations, the characteristic polynomial of the matrix D_{t} can be written as

C (x) = (x^{2} − V_{t}x + 1) (x − 1)^{2}

whose roots are α^{t}, β^{t} and 1.

The matrix D_{t} has linear dependent eigenvectors for both cases of t. So we cannot diagonalize the matrix D_{t}.

For later use, we define a triangular matrix and then we compute its nth power. Let t, r, s and m be arbitrary real numbers. Define two (4 × 4) upper triangular matrices H (r_{1}, r_{2}, r_{3}, r_{4}) and W_{n} by

H (r_{1}, r_{2}, r_{3}, r_{4}) = [ \begin{matrix}r_{1} & 0 & 0 & 0 \\ 1 & r_{2} & 0 & 0 \\ 1 & 0 & r_{3} & 0 \\ 1 & 0 & 0 & r_{4} \end{matrix} ]

and

W_{n} = [ \begin{matrix}r_{1}^{n} & 0 & 0 & 0 \\ f_{n} (r_{1}, r_{2}) & r_{2}^{n} & 0 & 0 \\ f_{n} (r_{1}, r_{3}) & 0 & r_{3}^{n} & 0 \\ f_{n} (r_{1}, r_{4}) & 0 & 0 & r_{4}^{n} \end{matrix} ] , n > 0,

where f_{n} (x, y) is the simple symmetric function f_{n} (x, y) = ∑_{i=0}^{n−1} x^{n−i}y^{i}.

By induction we can get easily the following lemma.

Lemma 2. For n > 0,

H^{n} (r_{1}, r_{2}, r_{3}, r_{4}) = W_{n}.

Now we are going to give our first result for the even subscripted weighted sums.

Theorem 2. For n, r > 0,

∑_{i=1}^{n} (n − i) U_{2ri} = \frac{n (2U_{2r} − U_{4r}) + U_{2r(n+1)} − 2U_{2nr} + U_{2r(n−1)}}{(U_{4r} − 2)^{2}}

Proof. Solving the following equation

D_{2r}Λ = ΛH (1, α^{2r}, β^{2r}, 1) ,

we obtain the solution depending on one parameter. By taking the parameter as 1, we find the matrix Λ as follows:

Λ = [ \begin{matrix}V_{4r} + V_{2r} + 6 & α^{6r} & β^{6r} & 1 \\ V_{2r} + 5 & α^{4r} & β^{4r} & 1 \\ 4 & α^{2r} & β^{2r} & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] .

By a simple computation, we obtain det Λ = (2U_{2r} − U_{4r}) δ where δ = \sqrt{A^{2} − 4}. Since det Λ ≠ 0, we write

D_{2r}^{n}Λ = ΛH (1, α^{2r}, β^{2r}, 1)^{n} .

By Lemma 2, the nth power of the matrix H (1, α^{2r}, β^{2r}, 1) is given by

H (1, α^{2r}, β^{2r}, 1)^{n} = [ \begin{matrix}1 & 0 & 0 & 0 \\ ∑_{i=0}^{n−1} α^{2ri} & α^{2nr} & 0 & 0 \\ ∑_{i=0}^{n−1} β^{2ri} & 0 & β^{2nr} & 0 \\ n & 0 & 0 & 1 \end{matrix} ] .

Arranging the right side of D_{2r}^{n}Λ = ΛH (1, α^{2r}, β^{2r}, 1)^{n} , we have the following linear system:

(V_{4r} + V_{2r} + 6) d_{11} + (V_{2r} + 5) d_{12} + 4d_{13} + d_{14} = 6 + n + ∑_{i=0}^{n+2} V_{2ir}
α^{6r}d_{11} + α^{4r}d_{12} + α^{2r}d_{13} + d_{24} = α^{2nr+6r}
β^{6r}d_{11} + β^{4r}d_{12} + β^{2r}d_{13} + d_{34} = β^{2nr+6r}
d_{11} + d_{12} + d_{13} + d_{14} = 1

where D_{2r} = [d_{ij}] . By the Cramer solution of the above system and using (8), we get

d_{11} = \frac{B_{n+2,2r}}{B_{2,2r}} = \frac{((n + 2) (2U_{2r} − U_{4r}) + U_{2nr+6r} − 2U_{2nr+4r} + U_{2nr+2r})}{(U_{4r} − 2U_{2r})^{2}}

and so

∑_{i=1}^{n} (n − i) U_{2ri} = \frac{n (2U_{2r} − U_{4r}) + U_{2r(n+1)} − 2U_{2nr} + U_{2r(n−1)}}{(U_{4r} − 2)^{2}} .

As an example, we get

∑_{i=1}^{n} (n − i) F_{8i} = \frac{n (2F_{8} − F_{16}) + F_{8(n+1)} − 2F_{8n} + F_{8(n−1)}}{(F_{16} − 2)^{2}} .

Second, we derive a new formula for the odd subscripted weighted sums by the following Theorem.

Theorem 3. For n, r > 0,

∑_{i=1}^{n} (n − i) U_{(2r+1)i} = \frac{U_{(n+1)(2r+1)} + 2U_{n(2r+1)} + U_{(n−1)(2r+1)} − nU_{2(2r+1)} − 2U_{2r+1}}{V_{2r+1}^{2}} .

Proof. Solving the following equation

D_{2r+1}Λ_{1} = Λ_{1}H (1, α^{2r+1}, β^{2r+1}, 1)

we obtain the solution with one parameter. By taking the parameter as 1, we find

Λ_{1} = [ \begin{matrix}V_{4r+2} + V_{2r+1} + 6 & α^{6r+3} & β^{6r+3} & 1 \\ V_{2r+1} + 5 & α^{4r+2} & β^{4r+2} & 1 \\ 4 & α^{2r+1} & β^{2r+1} & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ] .

Since det Λ_{1} = U_{4r+2}V_{2r+1}δ ≠ 0 where δ = \sqrt{A^{2} − 4}, we write

D_{2r}^{n}Λ_{1} = Λ_{1}H (1, α^{2r}, β^{2r}, 1)^{n} .

By Lemma 2, the nth power of matrix H (1, α^{2r+1}, β^{2r+1}, 1) is as follows:

H (1, α^{2r+1}, β^{2r+1}, 1)^{n} = [ \begin{matrix}1 & 0 & 0 & 0 \\ ∑_{i=0}^{n−1} α^{(2r+1)i} & α^{n(2r+1)} & 0 & 0 \\ ∑_{i=0}^{n−1} β^{(2r+1)i} & 0 & β^{n(2r+1)} & 0 \\ n & 0 & 0 & 1 \end{matrix} ] .

Computing the right side of D_{2r}^{n}Λ = ΛH (1, α^{2r}, β^{2r}, 1)^{n} , we have the following linear system:

(V_{4r+1} + V_{2r+1} + 6) d_{11} + (V_{2r+1} + 5) d_{12} + 4d_{13} + d_{14} = 6 + n + ∑_{i=1}^{n+2} V_{i(2r+1)}
α^{6r+3}d_{11} + α^{4r+2}d_{12} + α^{2r+1}d_{13} + d_{24} = α^{(2r+1)(n+3)}
β^{6r}d_{11} + β^{4r+2}d_{12} + β^{2r+1}d_{13} + d_{34} = β^{(2r+1)(n+3)}
d_{11} + d_{12} + d_{13} + d_{14} = 1

where D_{2r} = [d_{ij}] . By the Cramer solution of the above system and from (12), we obtain

d_{11} = \frac{B_{n+2,2r}}{B_{2,2r}}
= \frac{δ (U_{(n+3)(2r+1)} + 2U_{(n+2)(2r+1)} + U_{(n+1)(2r+1)} − (n + 2) U_{2(2r+1)} − 2U_{2r+1})}{U_{4r+2}V_{2r+1}δ}

and so

∑_{i=1}^{n} (n − i) U_{(2r+1)i} = \frac{U_{(n+1)(2r+1)} + 2U_{n(2r+1)} + U_{(n−1)(2r+1)} − nU_{2(2r+1)} − 2U_{2r+1}}{V_{2r+1}^{2}} .

Thus the theorem is proved.

As an example of the above theorem, we mention

∑_{i=1}^{n} (n − i) F_{5i} = \frac{F_{5(n+1)} + 2F_{5n} + F_{5(n−1)} − nF_{10} − 2F_{5}}{L_{5}^{2}} .

4 Permanental Representations

This section is mainly devoted to derive relationships between permanents of certain matrices and the terms of the sequence {B_{n,t}} . For similar relationships between determinants or permanents of certain matrices and terms of certain recurrences, we can refer to [4, 5].

Define the n × n (k − 1)−superdiagonal matrix in the compact form:

M_{n} (e_{1}, e_{2}, …, e_{k}) = [ \begin{matrix}e_{1} & e_{2} & … & e_{k} & & & 0 \\ 1 & e_{1} & e_{2} & … & e_{k} \\ & 1 & ... & ... & ... & ... \\ & & ... & e_{1} & e_{2} & … & e_{k} \\ & & & 1 & e_{1} & e_{2} & ⋮ \\ & & & & 1 & e_{1} & e_{2} \\ 0 & & & & & 1 & e_{1} \end{matrix} ]

where e_{1}, e_{2}, …, e_{k} are arbitrary integers.

Define the kth order linear recurrence {z_{n}} as follows

z_{n} = e_{1}z_{n−1} + e_{2}z_{n−2} + … + e_{k}z_{n−k}, n > 0,

where z_{1−k} = z_{2−k} = … = z_{−1} = 0 and z_{0} = 1.

Then we have the following result.

Theorem 4. For n > 0,

perM_{n} (e_{1}, e_{2}, …, e_{k}) = z_{n}

where perM_{i} = z_{i} for 0 ≤ i ≤ k − 1.

Proof. Denote perM_{n} (e_{1}, e_{2}, …, e_{k}) by perM_{n}. Extending perM_{n} with respect to the last column by the Laplace expansion of permanent, then we obtain

perM_{n} = e_{1}perM_{n−1} + e_{2}perM_{n−2} + … + e_{k}perM_{n−k}.

Since the recurrence relations (and initial conditions) of perM_{n} and the sequence {z_{n}} are the same, the conclusion easily follows.

Denote 4−tuples (V_{2r} + 2, −2 (V_{2r} + 1) , V_{2r} + 2, −1) and (V_{2r+1} +2, −2V_{2r+1}, V_{2r+1} −2, 1) by w_{1} and w_{2}, respectively. Then we have the following corollary.

Corollary 6. For n > 0 and r > 0,

perM_{n} (v_{1}) = ∑_{i=1}^{n} (n − i) U_{2ir},

and for r ≥ 0

perM_{n} (v_{2}) = ∑_{i=1}^{n} (n − i) U_{i(2r+1)}.

5 Acknowledgments

The second author was partially supported by an NPS-RIP grant.

References

[1] W. Y. C. Chen and J.D. Louck, The combinatorial power of the companion matrix, Linear Algebra Appl. 232 (1996), 261–278.

[2] E. Kilic, Sums of the squares of terms of sequence {u_{n}}, Proc. Indian Acad. Sci. (Math. Sci.) 118 (1) 2008, 27–41.

[3] T. Koshy, Fibonacci and Lucas numbers with applications, Pure and Applied Mathematics Wiley-Interscience, New York, 2001.

[4] H. Minc, Permanents of (0, 1)-circulants, Canad. Math. Bull. 7 (2) (1964), 253–263.

[5] G. Strang, Introduction to Linear Algebra, 3rd ed., Wellesley-Cambridge, Wellesley MA, 2003.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 15A36. Keywords: Second order linear recurrences, weighted sums, generating matrix, permanent, generating functions.

(Concerned with sequence \underline{A001924}.)

Received August 19 2008; revised version received February 10 2009. Published in Journal of Integer Sequences, February 14 2009.

Return to Journal of Integer Sequences home page.