$(pm 1)$-invariant sequences and truncated Fibonacci sequences of the second kind

( ±1)-INVARIANT SEQUENCES AND TRUNCATED FIBONACCI SEQUENCES OF THE SECOND KIND

Gyoung-Sik Choi, Suk-Geun Hwang, and Ik-Pyo Kim

Abstract. In this paper we present another characterization of ( ±1)-invariant sequences. We also introduce truncated Fibonacci and Lucas sequences of the second kind and show that a sequence x ∈ R

^∞

is (−1)-invariant(1-invariant resp.) if and only if D ˆ

₀

x

˜ is perpendicular to every truncated Fibonacci(truncated Lucas resp.) sequence of the second kind where

D = diag(( −1)

⁰

, ( −1)

¹

, ( −1)

²

, . . .).

1. Introduction

Throughout this paper, let R ^∞ denote the innite dimensional real vector space consisting of all real sequences (x ₀ , x ₁ , x ₂ , . . .) ^T , and let P and D denote the Pascal matrix [ ( _i

j

) ], (i, j = 0, 1, 2, . . .) and the diagonal matrix diag(( −1) ⁰ , ( −1) ¹ , ( −1) ² , . . .) respectively. We also assume that every matrix in this paper is assumed to have innitely many rows and columns numbered 0, 1, 2, . . . unless otherwise specied. The classical binomial inversion formula states that for x, y ∈ R ^∞ , P Dx = y if and only if P Dy = x. Let F = (F 0 , F 1 , F 2 , . . .) ^T = (0, 1, 1, 2, 3, . . .) ^T and L = (L ₀ , L ₁ , L ₂ , . . .) ^T = (2, 1, 3, 4, . . .) ^T be the Fibonacci sequence and the Lucas sequence respectively. Then P DF = −F and P DL = L.

Thus, as a linear transformation of R ^∞ , P D has eigenvalues −1, 1. In fact,

−1 and 1 are the only eigenvalues of P D

because if λ ̸= ±1, then P Dx = λx has no nonzero solution. A sequence x ∈ R ^∞ is called a 1-invariant sequence if P Dx = x, a ( −1)-invariant

Received March 30, 2004.

2000 Mathematics Subject Classication: Primary 11B39, 11B50.

Key words and phrases: ( ±1)-invariant sequence, truncated Fibonacci sequence of the second kind.

This research was supported by Kyungpook National University Research Team

Fund, 2003.

sequence if P Dx = −x ([1]). Associated with the Pascal matrix P , let P

^→

denote the matrix dened by

P

^→

=



 

 

 

1 0 0 0 0 0 0 0 · · · 0 1 1 0 0 0 0 0 · · · 0 0 1 2 1 0 0 0 · · · 0 0 0 1 3 3 1 0 · · · .. . .. . .. . .. . .. . .. . .. . .. . . ..



 

 

  ,

where the row i, (i = 0, 1, 2, . . .), is that of the Pascal matrix P preceded by 0 ^T _i , the i-vector of zeros. Let

(1.1) Q = P +

[ 1 0 ^T 0 P ]

=



 

 

 

 

2 0 0 0 0 · · · 1 2 0 0 0 · · · 1 3 2 0 0 · · · 1 4 5 2 0 · · · 1 5 9 7 2 · · · .. . .. . .. . .. . .. . . ..



 

 

 

  .

Associated with Q, let Q ^→ denote the matrix dened by

Q

^→

=



 

 

 

 

2 0 0 0 0 0 0 0 0 · · · 0 1 2 0 0 0 0 0 0 · · · 0 0 1 3 2 0 0 0 0 · · · 0 0 0 1 4 5 2 0 0 · · · 0 0 0 0 1 5 9 7 2 · · · .. . .. . .. . .. . .. . .. . .. . .. . .. . . ..



 

 

 

  ,

where the row i is that of Q preceded by 0 ^T _i , (i = 0, 1, 2, . . .). Then e ^T [0, P

^→

] = F and e ^T Q

^→

= L where e = (1, 1, . . .) ^T ∈ R ^∞ . It is noted in [1] that

Q

^→

= P

^→

+

[ 1 0 0 ^T 0 0 P

^→

] .

For a matrix A whose row index set and column index set are J and K

respectively, and for J ₀ ⊂ J, K 0 ⊂ K, let A(J 0 |K 0 ) denote the matrix

obtained from A by deleting rows in J 0 and columns in K 0 , and let

A[J 0 |K 0 ] denote the matrix A(J 0 |K 0 ) where J 0 = J − J 0 , K 0 = K − K 0 .

In [4], generating functions of ( ±1)-invariant sequences are investi-

gated. In [1], the authors found some characterization of ( ±1)-invariant

sequences in connection with the matrices P and Q. They also in-

troduced truncated Fibonacci and Lucas sequences and proved that a

sequence x ∈ R ^∞ is ( −1)-invariant(1-invariant resp.) if and only if x

is expressible as a linear combination of truncated Fibonacci(truncated Lucas resp.) sequences.

In this paper we present another characterization of ( ±1)-invariant sequences. We also introduce truncated Fibonacci and Lucas sequences of the second kind and show that a sequence x ∈ R ^∞ is ( −1)-invariant(1- invariant resp.) if and only if D [ ₀

x

] is perpendicular to every truncated Fibonacci(truncated Lucas resp.) sequence of the second kind.

2. Relationship between ( ±1)-invariant sequences

In this section we rst investigate the relationship between ( ±1)- invariant sequences.

Lemma 2.1. [1] For a sequence x ∈ R ^∞ , the following hold.

(a) x is ( −1)-invariant if and only if P

^→

Dx = 0, (b) x is 1-invariant if and only if Q

^→

(0 |0)Dx = 0.

The matrices P

^→

and Q

^→

are related as Q

^→

= P

^→

+

[ 1 0 0 ^T 0 0 P

^→

] .

Yet, there is another relation between P

^→

and Q

^→

. In what follows let

N denote the matrix diag(1, 2, 3, 4, . . .).

Lemma 2.2. The matrices P

^→

and Q

^→

are related as Q

^→

=

[ 2 0 ^T 0 ⁻¹ _N

] P

^→

[ 1 0 ^T

0 _N

] .

Proof. Let P = [β _ij ], Q = [γ _ij ], (i, j = 0, 1, 2, . . .). Then β _ij = ( _i

j

) and, by (1.1),

(2.1) γ _ij = ( i

j )

+

( i − 1 j − 1 )

= i + j i

( i j

)

= i + j i β _ij

for i, j ≥ 1. Thus we see that Q is obtained from P by multiplying the row i by ¹ _i , (i = 1, 2, . . .) and multiplying each of the entries in the line i + j = k by k, (k = 1, 2, . . .) and then multiplying the row 0 by 2. Let

P

^→

= [p ₀ , p ₁ , p ₂ , . . .], Q

^→

= [q ₀ , q ₁ , q ₂ , . . .].

Then

p _k = (β _0,k , β _{1,k −1} , . . . , β _{k −1,1} , β _k,0 , 0, 0, . . .) ^T ,

q _k = (γ _0,k , γ _{1,k −1} , . . . , γ _{k −1,1} , γ _k,0 , 0, 0, . . .) ^T ,

for k = 1, 2, . . ., from which we see that q _k = (2kβ _0,k , kβ _{1,k −1} , 1

2 kβ _{2,k −2} , 1

3 kβ _{3,k −3} , . . . , 1

k kβ _k,0 , 0, 0, . . .) ^T , for k = 1, 2, . . ., by (2.1). Thus we have the equality in the Lemma.

The following theorem is a characterization of (±1)-invariant sequences which looks similar to but is dierent from Lemma 2 .1.

Theorem 2.3. Let x = (x 0 , x 1 , x 2 , . . .) ^T ∈ R ^∞ . Then

(a) x is ( −1)-invariant if and only if Q

^→

(x 0 , −x 1 , ¹ ₂ x 2 , − ¹ ₃ x 3 , . . .) ^T = 0.

(b) x is 1-invariant if and only if

P

^→

(0 |0)(x 0 , −2x 1 , 3x ₂ , −4x 3 , . . .) ^T = 0.

Proof. Since P

^→

Dx = 0 is equivalent to Q

^→

[ _{1 0}

^T

0

⁻¹_N

] Dx = 0 by Lemma 2.2, (a) follows from Lemma 2.1(a). By Lemma 2.2, we also have Q

^→

(0 |0) = ⁻¹ _N P

^→

(0 |0) N . So, Q

^→

(0 |0)Dx = 0 is equivalent to P

^→

(0|0) N Dx = 0, and (b) follows from Lemma 2.1(b).

We now present the relationship between the ( −1)-invariant sequences and the 1-invariant sequences.

Lemma 2.4. [1] Let (x 0 , x 1 , x 2 , . . .) ^T ∈ R ^∞ and let s k = ∑ _k

i=0 x i , (k = 0, 1, 2, . . .). Then (x ₀ , x ₁ , x ₂ , . . .) ^T is λ-invariant if and only if (0, 0, s 0 , s 1 , s 2 , . . .) ^T is λ-invariant, for λ ∈ {1, −1}.

Theorem 2.5. Let x = (x 0 , x 1 , x 2 , . . .) ^T ∈ R ^∞ . Then

(a) x is ( −1)-invariant if and only if x 0 = 0 and (x ₁ , ¹ ₂ x ₂ , ¹ ₃ x ₃ , ¹ ₄ x ₄ , . . .) ^T is 1-invariant.

(b) x is 1-invariant if and only if (0, x ₀ , 2x ₁ , 3x ₂ , . . .) ^T is ( −1)-invariant.

Proof. (a) Let y = (x 1 , x 2 , . . .) ^T so that x = [ _x

₀

y

] and Dx = [ _x

₀

−Dy ] . Suppose that x is (−1)-invariant. Then, by Lemma 2.1, P

^→

Dx = 0,

i.e., [

1 0 ^T

0 P

^→

(0 |0) ] [ x 0

−Dy ]

= [ 0

0 ]

. Thus x ₀ = 0 and

(2.2) P

^→

(0 |0)Dy = 0.

Now (2.2) gives us that

−1 N P

^→

(0 |0) N −1

N Dy = 0, i.e., Q

^→

(0 |0) ⁻¹ _N Dy = 0.

So, by Lemma 2.1 again we see that ⁻¹ _N y = (x 1 , ¹ ₂ x 2 , ¹ ₃ x 3 , ¹ ₄ x 4 , . . .) ^T is 1-invariant. Reversing the above argument we can show that if ⁻¹ _N y is 1-invariant, then x is ( −1)-invariant.

(b) Suppose that x is 1-invariant. Then, by Lemma 2.1, Q

^→

(0|0)Dx = 0 from which we get P

^→

(0 |0) N Dx = 0 so that

P

^→

[ 0

N Dx ]

=

[ 1 0 ^T 0 P

^→

(0 |0)

] [ 0

N Dx ]

= [ 0

0 ]

.

Since [

0

N Dx ]

= −D [ 0

N x ]

, we see, by Lemma 2.1, that [ ₀

N

x

] = (0, x 0 , 2x 1 , 3x 2 , 4x 3 , . . .) ^T is ( −1)- invariant. Reversing the above argument, it can be shown that if [ ₀

N

x

] is ( −1)-invariant, then x is 1-invariant.

3. ( ±1)-invariant sequences and the truncated Fibonacci and Lucas sequences

In [1], [2], and [3], some generalization of Fibonacci and Lucas se- quences are found. In this section we introduce another extension of the notion of Fibonacci and Lucas sequences.

Suppose that we arrange n congruent cubic blocks in such a way that the blocks are arranged in one or two rows and each of the blocks in the top row(top blocks) is placed on a block in the bottom row(base block). We call such an arrangement a Fibonacci arrangement of n blocks. Let F n denote the set of all Fibonacci arrangements of n blocks.

It is well known that |F n |, the number of elements of F n , is equal to ( _n

0

) + ( _{n −1}

1

) + · · · + ( ₁

n −1

) + ( ₀

n

) = F _n+1 , the (n + 1)st Fibonacci number.

For a nonnegative integer r, let F r,n denote the set of all Fibonacci arrangements of n blocks in such a way that the number of top blocks is ≤ r. The sequence F r = (f r,0 , f r,1 , f r,2 , . . .) ^T dened by f r,0 = 0, f _r,1 = 1, f _r,n = |F r,n −1 |, the number of elements of F r,n −1 , (n ≥ 2) is called rth truncated Fibonacci sequence ([1]). It is noted in [1] that f r,n+1 = ∑ _r

k=0

( _{n −k}

k

) which is the sum of entries of P lying on the line i + j = n within the range 0 ≤ j ≤ r.

Consider the set F r,n ^′ of all Fibonacci arrangements of n blocks such that the number of base blocks is ≤ r. Let F ^′ r = (f _r,0 ^′ , f _r,1 ^′ , f _r,2 ^′ , . . .) ^T be dened by

f _r,0 ^′ = 0, f _r,1 ^′ = 1, f _r,n ^′ = |F r,n ^′ −1 |, (n ≥ 2).

We call F ^′ _r the rth truncated Fibonacci sequence of the second kind. Let k be the number of base blocks in an arrangement in F r,n ^′ . Then the number of top blocks is n − k, and there are ( _k

n −k

) ways that the n − k top blocks can be placed. Since 0 ≤ k ≤ r, we have

f _r,n+1 ^′ = ( 0

n )

+ ( 1

n − 1 )

+ · · · + ( r

n − r )

,

which is the sum of entries of P lying on the line i + j = n within the range 0 ≤ i ≤ r. Therefore we see that F ^′ _r is the column sum vector of [0, P

^→

[0, 1, . . . , r |0, 1, 2, . . .]].

Let Q = [γ _ij ] and let g _r,n = ∑ _r

k=0 γ _{n −k,k} and L _r = (g _r,0 , g _r,1 , g _r,2 , . . .) ^T . Then g r,n is equal to the sum of the entries of Q lying on the line i+j = n within the range 0 ≤ j ≤ r. The sequence L r is called the rth truncated Lucas sequence ([1]).

Let

(3.1) g _r,n ^′ =

∑ r k=0

γ _{k,n −k}

and let L ^′ _r = (g _r,0 ^′ , g _r,1 ^′ , g _r,2 ^′ , . . .) ^T . We call L ^′ _r the rth truncated Lucas sequence of the second kind. Since the right hand side of (3.1) is the sum of the entries of Q lying on the line i + j = n within the range 0 ≤ i ≤ r, we see that L ^′ _r is the column sum vector of Q

^→

[0, 1, . . . , r |0, 1, 2, . . .].

A sequence x = (x ₀ , x ₁ , x ₂ , . . .) ^T ∈ R ^∞ is called a finite sequence if x i = 0 for all but a nite number of i’s. Note that the sequences F ^′ _r and L ^′ _r are nite sequences for all r.

It is proved in [1] that a sequence is ( −1)-invariant (1-invariant resp.) if and only if it is expressible as a linear combination of truncated Fibonacci(truncated Lucas resp.) sequences. In particular, the trun- cated Fibonacci(truncated Lucas resp.) sequences are (−1)-invariant (1-invariant resp.) sequences.

Are the truncated Fibonacci and the truncated Lucas sequences of the second kind (±1)-invariant sequences?

The answer to this question is given in the following

Theorem 3.1. No nonzero (±1)-invariant sequence is a nite se- quence.

Proof. Let x = (x ₀ , x ₁ , x ₂ , . . .) ^T ∈ R ^∞ be a nite sequence. Take

an integer m such that x i = 0 for all i > m. Let n = 2m and let

y = (x ₀ , x ₁ , . . . , x _m ) ^T so that x = (y ^T , x _m+1 , x _m+2 , . . .) ^T . Suppose that

x is ( −1)-invariant. Then P

^→

Dx = 0 by Lemma 2.1 and hence

P

^→

[0, 1, . . . , m |0, 1, . . . , n]D n

[ _y

0

m

] = 0

where D n = diag((−1) ⁰ , (−1) ¹ , · · · , (−1) ⁿ ) and 0 m denotes the m-vector of zeros. Since P

^→

[0, 1, . . . , m |0, 1, . . . , n] has rank m + 1, we have that D _m y = 0 and hence that y = 0 so that x = 0.

Though the truncated Fibonacci and the truncated Lucas sequences of the second kind are not ( ±1)-invariant sequences, they still retain sub- stantial importance in determining whether a sequence is ( ±1)-invariant or not.

Theorem 3.2. Let x ∈ R ^∞ . Then

(a) x is ( −1)-invariant if and only if (F ^′ r ) ^T D [ ₀

x

] = 0 for all r = 0, 1, 2, . . ..

(b) x is 1-invariant if and only if (L ^′ _r ) ^T D [ ₀

x

] = 0 for all r = 0, 1, 2, . . ..

Proof. (a) Let

=



 

 

 

1 0 0 0 · · · 1 1 0 0 · · · 1 1 1 0 · · · 1 1 1 1 · · · .. . .. . .. . .. . . ..



 

 

  , F ^′ =



 

  (F ^′ ₀ ) ^T (F ^′ ₁ ) ^T (F ^′ ₂ ) ^T

.. .



 

  .

Then F ^′ = [ 0, P

^→

]. Let x ∈ R ^∞ . Suppose that x is (−1)-invariant.

Then P

^→

Dx = 0 so that F ^′ D [ ₀

x

] = 0, proving the ‘only if’ part of (a).

Conversely suppose that F ^′ D [ ₀

x

] = 0. Then P

^→

Dx = 0. Let

=



 

 

 

1 0 0 0 · · ·

−1 1 0 0 · · · 0 −1 1 0 · · · 0 0 −1 1 · · · .. . .. . .. . .. . . ..



 

 

  .

Then = diag(1 , 1, . . .) and we get P

^→

Dx = P

^→

Dx = 0, which tells us that x is ( −1)-invariant by Lemma 2.1(a), and the proof of (a) is complete.

(b) Let

L ^′ =



 

  (L ^′ ₀ ) ^T (L ^′ ₁ ) ^T (L ^′ ₂ ) ^T

.. .



 

  .

Then L ^′ = Q

^→

. Let x ∈ R ^∞ . Suppose that x is 1-invariant. Then Q

^→

(0 |0)Dx = 0 so that

Q

^→

[ 0

Dx ]

= [ 0

0 ]

. But then

L ^′ [ 0

Dx ]

= [ 0

0 ]

, which yields that

L ^′ D [ ₀

x

] = 0

and the ‘only if’ part of (b) is proved. The ‘if’ part can be proved by reversing the above argument.

4. Some properties of truncated Fibonacci and Lucas se- quences of the second kind

In this section we give a couple of sequential properties of truncated Fibonacci and Lucas sequences of the second kind. In the sequel, we assume, for integers i, j, that ( _i

j

) = 0 if either i < 0 or j < 0 or i < j.

Theorem 4.1. Let r be a positive integer. Then (a) f _r,n ^′ = f _r,n ^′ ₋₁ + f _r,n ^′ ₋₂ − ( _r+1

n −r−2

) , (n ≥ 2).

(b) g _r,n ^′ = g _r,n ^′ ₋₁ + g ^′ _{r,n −2} − _r+1 ⁿ ( _r+1

n −r−1

) , (n ≥ 2).

Proof. (a) By the denition of the numbers f _r,n ^′ , we have f _r,n−1 ^′ + f _r,n−2 ^′ =

( 0 n − 2

) +

( 1 n − 3

)

+ · · · +

( r

n − r − 2 )

+ ( 0

n − 3 )

+ ( 1

n − 4 )

+ · · · +

( r

n − r − 3 )

= ( 1

n − 2 )

+ ( 2

n − 3 )

+ · · · +

( r + 1 n − r − 2

)

=

∑ r k=0

( k

n − k − 1 )

+

( r + 1 n − r − 2

)

= f _r,n ^′ +

( r + 1 n − r − 2

) , since ( ₀

n −1

) = 0 for n ≥ 2.

(b) Let Q = [γ ij ]. Then γ i,j + γ i,j+1 = γ i+1,j+1 for all i, j = 0, 1, 2, . . ., and γ _ij = 0 if i < j. Let δ _ij be a number dened for every pair ( i, j) of integers by

δ _ij =

{ γ _ij if i, j ≥ 0,

0 if either i < 0 or j < 0.

Then δ _i,j + δ _i,j+1 = δ _i+1,j+1 for all i, j, and

g _r,n ^′ ₋₁ + g ^′ _{r,n −2} = δ _{0,n −1} + δ _{1,n −2} + · · · + δ r,n −r−1

+ δ 0,n −2 + δ 1,n −3 + · · · + δ r,n −r−2

= δ 1,n −1 + δ 2,n −2 + · · · + δ r+1,n −r−1

= g ^′ _r,n + δ _{r+1,n −r−1} . If n ≥ r + 2, then

δ _{r+1,n−r−1} = γ _{r+1,n−r−1} =

( r + 1 n − r − 1

) +

( r

n − r − 2 )

= n

r + 1

( r + 1 n − r − 1

) . If n = r + 1, then

δ _{r+1,n −r−1} = 1 = n r + 1

( r + 1 n − r − 1

) . If n < r + 1, then

δ _{r+1,n −r−1} = 0 = n r + 1

( r + 1 n − r − 1

) . Thus (b) is proved.

As nite sequences, the truncated Fibonacci and Lucas sequences of the second kind have nite sums which look very simple as we see in the following

Theorem 4.2. Let r be a nonnegative integer. Then (a) ∑ _∞

n=0 f _r,n ^′ = 2 ^r+1 − 1.

(b) ∑ _∞

n=0 g _r,n ^′ = 3 · 2 ^r − 1.

Proof. (a) ∑ _∞

n=0 f _r,n ^′ is equal to the sum of all entries ( _i

j

) of P in the range 0 ≤ i ≤ r. Therefore ∑ _∞

n=0 f _r,n ^′ = ∑ _r

i=0 2 ⁱ = 2 ^r+1 − 1.

(b) ∑ _∞

n=0 g _r,n ^′ is equal to the sum of all entries γ ij of Q in the range 0 ≤ i ≤ r. Since Q = P + [ _{1 0}

T

0 P

] we see that

∑ ∞ n=0

g ^′ _r,n =

∑ r i=0

2 ⁱ + 1 +

r −1

∑

i=0

2 ⁱ = 2 ^r+1 − 1 + 1 + 2 ^r − 1 = 3 · 2 ^r − 1.

Our last discussion is the relationship between the Fibonacci(Lucas resp.) sequence and the truncated Fibonacci(truncated Lucas resp.) se- quences of the second kind.

Since the Fibonacci sequence F = (F ₀ , F ₁ , F ₂ , . . .) ^T and the Lucas se- quence L = (L ₀ , L ₁ , L ₂ , . . .) ^T are ( −1)-invariant and 1-invariant respec- tively, it follows, from Theorem 3.2, that

∑ ∞ n=1

( −1) ⁿ f _r,n ^′ F _{n −1} = 0, (r = 0, 1, 2, . . .)

and ∑ ∞

n=1

( −1) ⁿ g _r,n ^′ L _{n −1} = 0, (r = 0, 1, 2, . . .).

Since, for i ≥ 1, γ _{i,n −i} =

( i n − i

) +

( i − 1 n − i − 1

)

= n i

( i n − i

) , we see, by the denition of g _r,n ^′ , that for n ≥ 1,

g ^′ _r,n =

∑ r i=0

γ _{i,n −i} =

∑ r i=1

γ _{i,n −i} =

∑ r i=1

n i

( i n − i

) . So we have the following

Theorem 4.3. The Fibonacci and Lucas sequences satisfy the fol- lowing relations.

(a) ∑ _∞

n=0 ( −1) ⁿ⁺¹ F n

∑ _r

i=0

( _i

n −i

) = 0.

(b) ∑ _∞

n=0 ( −1) ⁿ⁺¹ L _n (n + 1) ∑ _r

i=1 1 i

( _i

n −i+1

) = 0.

References

[1] G.-S. Choi, S.-G. Hwang, and I.-P. Kim, ( ±1)-Invariant sequences and truncated Fibonacci sequences, submitted.

[2] G.-Y. Lee, k-Lucas numbers and associated bipartite graphs, Linear Algebra Appl.

320 (2000), 51–61.

[3] G.-Y. Lee, S.-G. Lee and H.-G. Shin, On the k-th generalized Fibonacci matrix

Q

k

, Linear Algebra Appl. 251 (1997), 73–88.

[4] Z.-H. Sun, Invariant sequences under binomial transformation, Fibonacci Quart.

39 (2001), 324–333.

Gyoung-Sik Choi, Suk-Geun Hwang, and Ik-Pyo Kim Department of Mathematics Education

Kyungpook University Daegu, 702-701, Korea

E-mail : [email protected]

[email protected]

[email protected]