Linear recurrences and Chebyshev polynomials

April 28, 2003

Sergey Kitaev and Toufik Mansour ^{1}

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

           kitaev@math.chalmers.se, toufik@math.chalmers.se

1 Introduction and the main result

As usual, Fibonacci polynomials F_{n}(x), Lucas polynomials L_{n}(x), and Pell polynomials P_{n}(x) are defined by the second-order linear recurrence

t_{n+2} = at_{n+1} + bt_{n},  (1)

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

1 INTRODUCTION AND THE MAIN RESULT 2 with given a, b, t_{0}, t_{1} and n ≥ 0. This sequence was introduced by Horadam [3] in 1965, and it generalizes many sequences (see [1, 4]). Examples of such sequences are Fibonacci polynomials sequence (F_{n}(x))_{n≥0}, Lucas polynomials sequence (L_{n}(x))_{n≥0}, and Pell polynomials sequence (P_{n}(x))_{n≥0}, when one has a = x, b = t_{1} = 1, t_{0} = 0; a = t_{1} = x, b = 1, t_{0} = 2; and a = 2x, b = t_{1} = 1, t_{0} = 0; respectively. Chebyshev polynomials of the second kind (in this paper just Chebyshev polynomials) are defined by

U_{n}(cos θ) = \frac{sin(n + 1)θ}{sin θ}

for n ≥ 0. Evidently, U_{n}(x) is a polynomial of degree n in x with integer coefficients. For example, U_{0}(x) = 1, U_{1}(x) = 2x, U_{2}(x) = 4x^{2} −1, and in general (see Recurrence 1 for a = 2x, b = −1, t_{0} = 1, and t_{1} = 2x), U_{n+2}(x) = 2xU_{n+1}(x) − U_{n}(x). Chebyshev polynomials were invented for the needs of approximation theory, but are also widely used in various other branches of mathematics, including algebra, combinatorics, and number theory (see [5]).

Lemma 1.1 Let (t_{n})_{n≥0} be any sequence that satisfies t_{n+2} = 2x · t_{n+1} − t_{n} with given t_{0}, t_{1}, and n ≥ 0. Then for all n ≥ 0,

t_{n} = t_{1} · U_{n−1}(x) − t_{0} · U_{n−2}(x),

where U_{m} is the mth Chebyshev polynomial of the second kind.

1 INTRODUCTION AND THE MAIN RESULT 3 Proof. A proof is straightforward using the relation U_{n+2}(x) = 2xU_{n+1}(x) − U_{n}(x) and induction on n. □

Let A be a tile of size 1 × 1 and B be a tile of size 1 × 2. We denote by 𝔏_{n} the set of all tilings of a 1 × n rectangle with tiles A and B. An element of 𝔏_{n} can be written as a sequence of the letters A and B. For example, 𝔏_{1} = {A}, 𝔏_{2} = {AA, B}, and 𝔏_{3} = {AAA, AB, BA}. We denote by |α| the number of tiles A and B in α. For example, |AAA| = 3 and |AB| = 2.

Proposition 1.2 The number of tilings of a 1 × n rectangle with tiles A and B is the Fibonacci number F_{n+1}, that is, |𝔏_{n}| = F_{n+1}.

Proof. The result is immediate for n ≤ 1, so it is sufficient to show that the number of such tilings satisfies the recurrence F_{m} = F_{m−1} + F_{m−2}. To do this, we observe that there is a one-to-one correspondence between the tilings of a 1 × (n − i) rectangle and the tilings of a 1 × n rectangle in which the rightmost tile has length i, where i = 1, 2. Therefore, if we count tilings of a 1×n rectangle according to the length of the rightmost tile, we find the number of such tilings satisfies the recurrence F_{m} = F_{m−1} + F_{m−2}, as desired. □

Let α be any element of 𝔏_{n}, we define β by β_{i} = 1 if α_{i} = A; otherwise β_{i} = 2, and we write β = χ(α). For example, χ(AAABAB) = 111212. Now, let us fix an integer s and a natural number q such that q ≥ 1. Let a_{0}, a_{1}, …, a_{q−1}, b_{0}, b_{1}, …, b_{q−1} be 2q constants and a = (a_{0}, a_{1}, …, a_{q−1}), b = (b_{0}, b_{1}, …, b_{q−1}). For any α ∈ 𝔏_{n}, we define v(n; s) = v_{a,b}(n; α, q, s) = ∏_{i=1}^{|α|} k(β_{i}) where

k(β_{i}) = \{ \begin{matrix}a_{(s+β_{1}+···+β_{i}) mod q}, & if β_{i} = 1, \\ b_{(s+β_{1}+···+β_{i}) mod q}, & if β_{i} = 2, \end{matrix}

and β = χ(α). For example, if q = 3, a_{n} = n and b_{n} = 1 for n = 0, 1, 2, s = 0, and α = AABAB, then we have that

v_{a,b}(n; α, q, s) = a_{1 mod 3}a_{2 mod 3}b_{4 mod 3}a_{5 mod 3}b_{7 mod 3} = a_{1}a_{2}b_{1}a_{2}b_{1} = a_{1}a_{2}^{2} = 4.

We will be interestes in the sum of all v_{a,b}(n; α, q, s) over all α ∈ 𝔏_{n}, which is denoted by V (n; s) = V_{a,b}(n; q, s), that is, V (n; s) = ∑_{α∈𝔏_{n}} v_{a,b}(n; α, q, s). For example, V (1; s) = a_{(s+1) mod q} and V (2; s) = a_{(s+1) mod q}a_{(s+2) mod q} +b_{(s+2) mod q}. We extend the definition of V (n; s) as V (0; s) = 1 and V (n; s) = 0 for n < 0. We remark that V (n; q, s) can be given by a combinatorial interpretation as follows: V (n; q, s) counts the number of ways to tile a boards of length n, with cells numbered s+1 through s+n, using colored tiles of size 1 × 1 and tiles of size 1 × 2. For a tile of size 1 × 1 on cell i, we have a_{i mod q} color choices; and for a tile of size 1 × 2 on cells i − 1 and i, we have b_{i mod q} choices. The main result of this paper can be formulated as follows.

Theorem 1.3 Let (x_{n})_{n≥0} be any sequence (x_{n} = x_{n;q}(a, b)) that satisfies

x_{qn+d} = a_{d} · x_{qn+d−1} + b_{d} · x_{qn+d−2},  (2)

2 PROOFS 5 for all n ≥ 1, 0 ≤ d ≤ q − 1, with given x_{0}, x_{1}, …, x_{q−1}. Then for n ≥ 1, x_{qn+d} is given by

\sqrt{−J_{q;d}}^{n−2} (x_{q+d}\sqrt{−J_{q;d}}U_{n−1}(w_{q;d}) + (x_{2q+d} − I_{q;d}x_{q+d}) · U_{n−2}(w_{q;d})) ,

for all n ≥ 1, where U_{m} is the mth Chebyshev polynomial,

\begin{matrix}x_{q+d} = V (d + 1; −1)x_{q−1} + b_{0}V (d; 0)x_{q−2} \\ x_{2q+d} = V (q + d + 1; −1)x_{q−1} + b_{0}V (q + d; 0)x_{q−2}, \end{matrix}

and

\begin{matrix}w_{q;d} = \frac{I_{q;d}}{2\sqrt{−J_{q;d}}} , \\ I_{q;d} = b_{(d+1) mod q} · V (q − 2; d + 1) + V (q; d), \\ J_{q;d} = b_{(d+1) mod q} · (V (q − 1; d + 1)V (q − 1; d) − V (q; d)V (q − 2; d + 1)). \end{matrix}  (3)

The paper is organized as follows. In Section 2 we give a proof of Theorem 1.3, and in Section 3 we give some applications for Theorem 1.3.

2 Proofs

Throughout this section, we assume that q is a natural number (q ≥ 1) and s is an integer. Also, let a_{0}, a_{1}, …, a_{q−1}, b_{0}, b_{1}, …, b_{q−1} be 2q constants and a = (a_{0}, a_{1}, …, a_{q−1}), b = (b_{0}, b_{1}, …, b_{q−1}). We start from the following lemma.

Lemma 2.1 Let ℓ be an integer such that ℓ ≥ s + 2. Then

V (ℓ − s; s) = a_{ℓ mod q} · V (ℓ − s − 1; s) + b_{ℓ mod q} · V (ℓ − s − 2; s).

Proof. To verify this lemma, we observe that there is a one-to-one correspondence between the tilings of a 1 × (ℓ − s − i) rectangle and the tilings of a 1 × (ℓ − s) rectangle in which the rightmost tile has length i, where i = 1, 2. Hence V (ℓ − s; s) = a_{ℓ mod q} · V (ℓ − s − 1; s) + b_{ℓ mod q} · V (ℓ − s − 2, s), where the first term corresponds to the case i = 1 and the second one to the case i = 2. □

Now, let us apply this lemma to find x_{qn+d+m} in terms of x_{qn+d} and x_{qn+d−1}.

Proposition 2.2 Let q − 1 ≥ d ≥ 0 and n ≥ 1. Then for all m ≥ 0,

x_{qn+d+m} = V (m; d) · x_{qn+d} + b_{(d+1) mod q} · V (m − 1; d + 1) · x_{qn+d−1}.

Proof. Let us prove this proposition by induction on m. Since

x_{qn+d+0} = 1 · x_{qn+d+0} + b_{(d+1) mod q} · 0 · x_{qn+d−1},

V (0; d) = 1 and V (m; d) = 0 for m < 0, we have that the proposition holds for m = 0. By Recurrence 2 we get

x_{qn+d+1} = a_{(d+1) mod q} · x_{qn+d} + b_{(d+1) mod q} · x_{qn+d−1}
= V (1; d) · x_{qn+d} + b_{(d+1) mod q} · V (0; d + 1) · x_{qn+d−1},

therefore the proposition holds for m = 1. Now, we assume that the proposition holds for 0, 1, …, m − 1, and prove that it holds for m. By induction hypothesis we have

x_{qn+d+m−2} = V (m − 2; d) · x_{qn+d} + b_{(d+1) mod q} · V (m − 3; d + 1) · x_{qn+d−1},

and

x_{qn+d+m−1} = V (m − 1; d) · x_{qn+d} + b_{(d+1) mod q} · V (m − 2; d + 1) · x_{qn+d−1},

hence, by Equation 2 we get

x_{qn+d+m} = a_{(d+m) mod q} · x_{qn+d+m−1} + b_{(d+m) mod q} · x_{qn+m+d−2} = (a_{(d+m) mod q} · V (m − 1; d) + b_{(d+m) mod q} · V (m − 2; d))x_{qn+d} +b_{(d+1) mod q}(a_{(d+m) mod q} · V (m − 2; d + 1) + b_{(d+m) mod q} · V (m − 3; d + 1))x_{qn+d−1}.

Using Lemma 2.1 for ℓ = m + d, s = d and for ℓ = m + d, s = d + 1, we get the desired result. □

Now we introduce a recurrence relation that plays the crucial role in the proof of the Main Theorem.

Proposition 2.3 Let q − 1 ≥ d ≥ 0. Then for all n ≥ 2,

\begin{matrix}x_{q(n+1)+d} = (b_{(d+1) mod q} · V (q − 2; d + 1) + V (q; d))x_{qn+d} \\ +b_{(d+1) mod q} · (V (q − 1; d + 1)V (q − 1; d) − V (q; d)V (q − 2; d + 1))x_{q(n−1)+d}. \end{matrix}

Proof. Using Proposition 2.2 for m = q − 1 we get

x_{q(n+1)+d−1} − b_{(d+1) mod q} · V (q − 2; d + 1) · x_{qn+d−1} = V (q − 1; d) · x_{qn+d}, (4)

and for m = q we have

x_{q(n+1)+d} = V (q; d) · x_{qn+d} + b_{(d+1) mod q} · V (q − 1; d + 1) · x_{qn+d−1}.  (5)

Hence, Equation 4 yields

x_{q(n+1)+d} − b_{(d+1) mod q} · V (q − 2; d + 1) · x_{qn+d} = = V (q; d)(x_{qn+d} − b_{(d+1) mod q} · V (q − 2; d + 1) · x_{qn+d}) +b_{(q+1) mod q} · V (q − 1; d + 1)(x_{qn+d−1} − b_{(d+1) mod q} · V (q − 2; d + 1) · x_{q(n−1)+d−1}),

and by using Equation 4 we get the desired result. □

Proof of Theorem 1.3. Recall the definitions in 3. Now we are ready to prove the main result of this paper. Using Proposition 2.3 we have for n ≥ 2,

x_{q(n+1)+d} = I_{q;d} · x_{qn+d} + J_{q;d} · x_{q(n−1)+d}.

If we define t_{n} = x_{qn+d} for n ≥ 1, then we get

t_{n+1} = I_{q;d} · t_{n} + J_{q;d} · t_{n−1},

therefore, by defining (−J_{q;d})^{n/2}t′_{n} = t_{n} we have for n ≥ 2,

t′_{n+1} = 2w_{q;d}t′_{n} − t′_{n−1}.

Let us find expressions for t′_{0} and t′_{1}. By the recurrence for t_{n} we can define t_{0} as t_{2} = I_{q;d}t_{1} + J_{q;d}t_{0}, which means that t′_{0} = t_{0} = \frac{1}{J_{q;d}} (x_{2q+d} − I_{q;d}x_{q+d}). By definitions, t′_{1} = \frac{x_{q+d}}{\sqrt{−J_{q;d}}}. Using Proposition 2.2, we get x_{q+d} = V (d + 1; −1)x_{q−1} + b_{0}V (d; 0)x_{q−2} and x_{2q+d} = V (q + d + 1; −1)x_{q−1} + b_{0}V (q + d; 0)x_{q−2}. Hence, using Lemma 1.1 we get the desired result.

3 Applications

There is a connection between the sequences which are defined by Recurrence 2, and the sequences which are define by Recurrence 1. Indeed, from Theorem 1.3 we get the 3 APPLICATIONS 10 following result.

Corollary 3.1 For given x_{0} and x_{−1}, and the recurrence x_{n+2} = a_{0}x_{n+1} + b_{0}x_{n}, an explicit solution for this recurrence is given by

x_{n} = \sqrt{−b_{0}}^{n−2} [\sqrt{−b_{0}}(a_{0}x_{0} + b_{0}x_{−1})U_{n−1} (\frac{a_{0}}{2\sqrt{−b_{0}}} ) + b_{0}x_{0}U_{n−2} (\frac{a_{0}}{2\sqrt{−b_{0}}} )] ,

where U_{m} is the mth Chebyshev polynomial.

Proof. Using Theorem 1.3 for q = 1 with the parameters d = 0, I_{1;0} = a_{0}, J_{1;0} = b_{0}, x_{1} = a_{0}x_{0} + b_{0}x_{−1}, x_{2} = (a_{0}^{2} + b_{0})x_{0} + a_{0}b_{0}x_{−1}, and w_{1;0} = \frac{a_{0}}{2\sqrt{−b_{0}}} , we get the explicit solution for the recurrence x_{n+2} = a_{0}x_{n+1} + b_{0}x_{n}, as requested. □ The first interesting case is q = 2. Then Recurrence 2 gives

\{ \begin{matrix}x_{2n} & = a_{0}x_{2n−1} + b_{0}x_{2n−2} \\ x_{2n+1} & = a_{1}x_{2n} + b_{1}x_{2n−1}, \end{matrix}  (6)

with given x_{0} and x_{1}. In this case we have two possibilities: either d = 0 or d = 1. Let d = 0, so the parameters of the problem are given by I_{2;0} = a_{0}a_{1} +b_{0} +b_{1}, J_{2;0} = −b_{0}b_{1}, w_{2;0} = \frac{a_{0}a_{1}+b_{0}+b_{1}}{2\sqrt{b_{0}b_{1}}} , x_{2} = a_{0}x_{1} + b_{0}x_{0}, and x_{4} = (a_{0}^{2}a_{1} + a_{0}b_{1} + a_{0}b_{0})x_{1} + (a_{0}b_{0}a_{1} + b_{0}^{2})x_{0}. Hence, Theorem 1.3 gives the following result.

Corollary 3.2 The solution x_{2n} for Recurrence 6 is given by

\sqrt{b_{0}b_{1}}^{n−2} [\sqrt{b_{0}b_{1}}(a_{0}x_{1} + b_{0}x_{0})U_{n−1} (\frac{a_{0}a_{1} + b_{0} + b_{1}}{2\sqrt{b_{0}b_{1}}} ) − b_{0}b_{1}x_{0}U_{n−2} (\frac{a_{0}a_{1} + b_{0} + b_{1}}{2\sqrt{b_{0}b_{1}}} )] ,

where U_{m} is the mth Chebyshev polynomial.

Example 3.3 If x_{0} = 0, x_{1} = 1, a_{0} = x, a_{1} = xy, and b_{0} = b_{1} = 1, then the explicit expression to x_{2n} for the Recurrence 6 is given by xU_{n−1} (1 + \frac{1}{2}x^{2}y). Hence, by the definition it is easy to see that in the case y = 1, we have that the Fibonacci polynomial F_{2n}(x) is given by xU_{n−1} (1 + \frac{1}{2}x^{2}). If x_{0} = 2, x_{1} = 1, a_{0} = x, a_{1} = xy, and b_{0} = b_{1} = 1, then an explicit expression to x_{2n} for the Recurrence 6 is given by (x + 2)U_{n−1} (1 + \frac{1}{2}x^{2}y) − 2U_{n−2} (1 + \frac{1}{2}x^{2}y). Hence, in the case y = 1 we have that the Lucas polynomial L_{2n}(x) is given by (x + 2)U_{n−1} (1 + \frac{1}{2}x^{2}) − 2U_{n−2} (1 + \frac{1}{2}x^{2}). If x_{0} = 0, x_{1} = 1, a_{0} = 2x, a_{1} = yx, and b_{0} = b_{1} = 1, then an explicit expression to x_{2n} for the Recurrence 6 is given by 2xU_{n−1}(1 + x^{2}y). Hence, in the case y = 2 we have that the Pell polynomial P_{2n}(x) is given by 2xU_{n−1}(1 + 2x^{2}).

Another example for Theorem 1.3 is when q = 3 and d = 0. In this case the parameters of the problem are given by I_{3;0} = a_{0}a_{1}a_{2} + b_{0}a_{1} + b_{1}a_{2} + a_{0}b_{2}, J_{3;0} = b_{0}b_{1}b_{2}, x_{3} = a_{0}x_{2} + b_{0}x_{1}, and x_{6} − I_{3;0}x_{3} = b_{0}b_{1}(x_{2} − a_{2}x_{1}). Therefore, we get the following result.

Corollary 3.4 The solution x_{2n} for Recurrence 2, when q = 3, is given by

\sqrt{−b_{0}b_{1}b_{2}}^{n−2} (\sqrt{−b_{0}b_{1}b_{2}}(a_{0}x_{2} + b_{0}x_{1})U_{n−1}(w) + b_{0}b_{1}(x_{2} − a_{2}x_{1})U_{n−2}(w)) ,

for all n ≥ 1, where w = \frac{a_{0}a_{1}a_{2}+a_{0}b_{2}+b_{0}a_{1}+b_{1}a_{2}}{2\sqrt{−b_{0}b_{1}b_{2}}} , and U_{m} is the mth Chebyshev polynomial.

For example, if we are interested in solving the recurrence

\{ \begin{matrix}x_{3n} & = x_{3n−1} + x_{3n−2} \\ x_{3n+1} & = x_{3n} + x_{3n−1} \\ x_{3n+2} & = yx_{3n+1} + x_{3n}, \end{matrix}

with x_{0} = 0 and x_{1} = x_{2} = 1, then by the above corollary we get that the solution x_{3n} for this recurrence is given by

2i^{n−1}U_{n−1}(−i(1 + y)) + i^{n−2}(1 − y)U_{n−2}(−i(1 + y)),

where i^{2} = −1. In particular, if y = 1 then we have that the (3n)th Fibonacci number, F_{3n}, is given by 2i^{n−1}U_{n−1}(−2i). Acknowledgment. The authors would like to thank the anonymous referee for careful reading of the manuscript.

References

[1] G.H. Hardy and E.M. Wright, An introduction to the Theory of Numbers, 4th ed. London, Oxford University Press, 1962.

[2] P. Haukkanen, A note on Horadam’s sequence, The Fibonacci Quarterly 40:4 (2002) 358–361.

REFERENCES 13

[3] A.F. Horadam, Generalization of a result of Morgado, Portugaliae Math. 44 (1987) 131–136.

[4] A.F. Horadam and J.M. Mahon, Pell and Pell-Locas Polynomials, The Fibonacci Quarterly 23:1 (1985) 7–20.

[5] Th. Rivlin, Chebyshev polynomials. From approximation theory to algebra and number theory, John Wiley, New York, 1990.

2000 Mathematics Subject Classification: Primary 11B83, 42C05; Secondary 11K31