Roland Bacher

Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle

Keywords: Chebyshev polynomial, continued fraction, binomial coefficient. Math. class: Primary: 33C45, Secondary: 11A55, 11B65

come

Introduction

refs: Watson-Whittacker, qq chose sur fractions continues, polys de Cheb.

Chebyshev polynomials of the first kind T 0 , T 1 , . . . and of the second kind U 0 , U 1 , . . . have recursive definitions given by T 0 (x) = 1, T 1 (x) = x, T n+1 (x) = 2xT n (x) -T n-1 (x), n ≥ 1, and by

U 0 (x) = 1, U 1 (x) = 2x, U n+1 (x) = 2xU n (x) -U n-1 (x), n ≥ 1.
We write in the sequel always simply T n , U n for T n (x), U n (x). The polynomial sequences T 0 , T 1 , . . . and U 0 , U 1 , . . . satisfy the same linear recursion relation with characteristic polynomial Z 2 -2xZ + 1. This implies easily the formulae

T n = x + √ x 2 -1 n + x - √ x 2 -1 n 2 (1)
1 and

U n = x + √ x 2 -1 n+1 -x - √ x 2 -1 n+1 2 √ x 2 -1 . ( 2
)
The identity 2 cos x cos nx = cos(n + 1)x + cos(n -1)x (together with the initial values T 0 = 1, T 1 = x) implies by an easy induction T n (cos x) = cos nx (which is often used for defining Chebyshev polynomials of the first kind). As a consequence, we have the identity

T nm = T n • T m .
(3)

For n ∈ N and d ≥ 1 we introduce the rational fraction

S n,d = S n,d (x) = n k=0 U d-1 • T (d+1) k k j=0 1 U d • T (d+1) j . ( 4
)
Theorem 1. [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] We have for all n ∈ N and for all d ≥ 1 the identity

S 2 n,d -2xS n,d + 1 =   n j=0 1 U d • T (d+1) j   2 .
(5)

Corollary 1.2 For x evaluated to a real number in R \ [-1, 1], the limit lim n+d→∞ S n,d exists and is given by the root sign(x) |x| -√ x 2 -1 (where sign(x) ∈ {±1} denotes the sign of x) closest to zero of X 2 -2xX + 1.

The following result expresses S n,d as a simple fraction:

Theorem 1.3 We have S n,d = U (d+1) n+1 -2 U (d+1) n+1 -1 .
Corollary 1.2 is now an almost immediate consequence of Formula (2) and Theorem 1.3.

Note that Formula (4), perhaps computed using iteratively (3), is perhaps better suited for computations than the simpler expression given by Theorem 1.3.

Finally we have the following result:

Theorem 1.4 We have U n U n+1 = [0; 2x -1, 1 (, 2(x -1), 1) n ] .
Theorem 1.3 and Theorem 1.4 together imply that the evaluation at an integer x ≥ 2 of S n,d is a convergent of the real quadratic surd 1,1,1,with minimal polynomial

X -2xX + 1 ∈ Z[X].
In a last only losely related part we study some identities involving binomial coefficients (obtained by expressing Chebyshev polynomials in terms of binomials coefficients and generalizing some of the previously obtained identities). They lead to the array of numbers Section 3 contains a proof of Theorem 1.1, 1.3 and 1.4. A final Section describes a few relations with binomial coefficients and studies a few features of the above analogue of Pascal's triangle.

1 -1 1 1 0 1 -1 1 1 1 1 0 2 2 1 -1 1 2 4 3 1 1 0 3 6 7 4 1 -1 1
2 Analogues of Vajda's identity for Chebyshev polynomials

Fibonacci numbers F 1 = F 2 = 1, F n+1 = F n + F n-1 satisfy Vajda's identity F n+i F n+j -F n F n+i+j = (-1) n F i F j .
The following result describes analogues for Chebyshev polynomials:

Theorem 2.1 We have the following identities for Chebyshev polynomials:

U n+i U n+j -U n-1 U n+1+i+j = U i U j T n+i T n+j -T n-1 T n+1+i+j = (1 -x 2 )U i U j T n+i U n+j -U n-1 T n+1+i+j = T i U j T n+i U n+j -T n-1 U n+1+i+j = -U i T j+2 T n+i T n+j -(x 2 -1)U n-1 U n-1+i+j = T i T j
The case i = j = 0 of the first identity specialises to the so-called Cassini-Simpson identity U 2 n -U n+1 U n-1 = 1 and implies Turan's inequality U 2 n (x) > U n+1 (x)U n-1 (x) for all real x. The last equation generalises the instance T 2 n -(x 2 -1)U 2 n-1 = 1 (corresponding to i = j = 0) of Pell's equation.

Only a few cases of the first identity will in fact be used in the sequel.

Proof of Theorem 2.1 We consider

R(n, i, j) = U n+i U n+j -U n-1 U n+1+i+j -U i U j .
We have to show that R(n, i, j) = 0 for all n ≥ 1 and for all i, j ∈ N.

Using the recursion relation U n+1 = 2xU n -U n-1 on all terms depending on i, respectively depending on j, we see that it is enough to prove the equalities R(n, i, j) = 0 for i, j ∈ {0, 1}. Using the obvious identity R(n, i, j) = R(n, j, i) we are left with three cases: R(n, 0, 0), R(n, 0, 1) and R(n, 1, 1). The computation

U 2 n -U n-1 U n+1 -U 2 0 = U n (2xU n-1 -U n-2 ) -U n-1 (2xU n -U n-1 ) -1 = U 2 n-1 -U n U n-2 -1 shows R(n, 0, 0) = R(n -1, 0, 0) for n ≥ 2. Similarly, U n+1 U n -U n-1 U n+2 -U 1 U 0 = (2xU n -U n-1 )U n -U n-1 (2xU n+1 -U n ) -2x = 2x(U 2 n -U n-1 U n+1 -1)
shows R(n, 1, 0) = R(n, 0, 1) = 2xR(n, 0, 0). Finally, the identities

U n+1 U n+1 -U n-1 U n+3 -U 2 1 = U n+1 (2xU n -U n-1 ) -U n-1 (2xU n+2 -U n+1 ) -4x 2 = 2x(U n+1 U n -U n-1 U n+2 -2x) show R(n, 1, 1) = 2xR(n, 1, 0). It is now enough to check that R(n, i, j) = 0 for n ∈ {1, 2} and i, j ∈ {0, 1}.
Proofs of the remaining identities are similar. 2

Remark 2.2 Short direct proofs of Theorem 2.1 can be obtained using Formulae ( 1) and (2).

3 Proof of Theorem 1.1, 1.3 and 1.4

Useful identities

The following result is well-known:

Lemma 3.1
We have for all d ≥ 1 the identity

xU d = U d-1 + T d+1 .
The proof is an easy induction left to the reader. 2

Lemma 3.2 We have for all d ≥ 1 the identity

U 2 d = U 2 d-1 + 2T d+1 U d-1 + 1.
Proof Using Lemma 3.1 and the recursive definition of U , Lemma 3.2 is equivalent to

U 2 d = U 2 d-1 + 2(xU d -U d-1 )U d-1 + 1 = -U 2 d-1 + (2xU d )U d-1 + 1 = -U 2 d-1 + (U d+1 + U d-1 )U d-1 + 1 = U d+1 U d-1 + 1
which is a special case of the first equality in Theorem 2.1. 2 Lemma 3.3 We have

2T d U n = U n+d + U n-d
for all n ∈ N and for all d ∈ {0, 1, . . . , n}.

Proof We set R(n, d) = 2T d U n -U n+d -U n-d .
Since T 0 = 1 and

T 1 = x we have R(n, 0) = R(n, 1) = 0. The identities R(n, d) = 2T d U n -U n+d -U n-d = 2(2xT d-1 -T d-2 )U n -(2xU n+d-1 -U n+d-2 ) -(2xU n-d+1 -U n-d+2 ) = 2xR(n, d -1) -R(n, d -2) finish the proof. 2 Lemma 3.4
We have for all n ≥ 1 the identity

U 2n-1 = 2T n U n-1 .
Proof Equality holds for n = 1. Using Lemma (3.1) we have for n ≥ 2 the identities

U 2n-1 -2T n U n-1 = U 2n-1 -2(xU n-1 -U n-2 )U n-1 = U 2n-1 -(2xU n-1 -U n-2 )U n-1 + U n-1 U n-2 = -U n U n-1 + U 2n-1 + U n-1 U n-2 = -(U 1+(n-1) U 1+(n-2) -U 1-1 U 1+1+(n-1)+(n-2) -U n-1 U n-2 ).
The last expression equals zero by the first identity of Theorem 2.1. 2 Lemma 3.5 We have

U (n-1)d-1 U n-1 • T d = U nd-1 U n-2 • T d
for all n ≥ 2 and for all d ≥ 1.

Proof The case n = 2 boils down U 2d-1 = 2U d-1 T d which holds by Lemma (3.4). Adding to 0 = (2T d U (n-1)d-1 -U (n-2)d-1 -U nd-1 )U n-2 • T d
which holds by Lemma (3.3) the induction hypothesis we get

0 = (2T d U (n-1)d-1 -U (n-2)d-1 -U nd-1 )U n-2 • T d +U (n-2)d-1 U n-2 • T d -U (n-1)d-1 U n-3 • T d = U (n-1)d-1 (2T d U n-2 • T d -U n-3 • T d ) -U nd-1 U n-2 • T d = U (n-1)d-1 U n-1 • T d -U nd-1 U n-2 • T d
which ends the proof. 2

Proof of Theorem 1.1

We prove first that equation ( 5) holds for n = 0. Multiplying the left-side of equation ( 5) by U 2 d , we get

U 2 d-1 -2xU d-1 U d + U 2 d = U 2 d-1 -U d-1 (U d+1 + U d-1 ) + U 2 d = U 2 d -U d-1 U d+1 = U 2 0 = 1
by applying the recursive definition of U i and the first identity of Theorem 2.1 with n = d, i = j = 0.

Setting x = T d+1 in equation ( 5) and dividing the result by U 2 d , we have now by induction

S n,d • T d+1 U d 2 -2T d+1 S n,d • T d+1 U 2 d + 1 U 2 d =   n+1 j=0 1 U d • T (d+1) j   2 (6)
where we have also used (3) on the right side. We rewrite now the obvious identity

S n+1,d = U d-1 + S n,d • T d+1 U d . ( 7
)
as

S n,d • T d+1 = U d S n+1,d -U d-1 . (8)
Using ( 8) the left side of (6) equals

U d S n+1,d -U d-1 U d 2 -2T d+1 U d S n+1,d -U d-1 U 2 d + 1 U 2 d = S 2 n+1,d -2 U d-1 U d S n+1,d + U 2 d-1 U 2 d -2 T d+1 U d S n+1,d + 2T d+1 U d-1 U 2 d + 1 U 2 d Since -2 U d-1 U d S n+1,d -2 T d+1 U d S n+1,d = -2xS n+1,d
by Lemma (3.1) and

U 2 d-1 U 2 d + 2T d+1 U d-1 U 2 d + 1 U 2 d = 1
by Lemma (3.2), we get finally S 2 n+1,d -2xS n+1,d + 1 for the left side of (6). This ends the proof. 2

Proof of Theorem 1.3

Equality holds obviously for n = 0. Applying the induction hypothesis to (7) we have to establish the equality

U d U (d+1) n+2 -2 U (d+1) n+2 -1 = U d-1 + U (d+1) n+1 -2 • T d+1 U (d+1) n+1 -1 • T d+1 equivalent to 0 = (U d U (d+1) n+2 -2 -U d-1 U (d+1) n+2 -1 )U (d+1) n+1 -1 • T d+1 -U (d+1) n+2 -1 U (d+1) n+1 -2 • T d+1 = U (d+1) n+2 -2-d U (d+1) n+1 -1 • T d+1 -U (d+1) n+2 -1 U (d+1) n+1 -2 • T d+1
where we have applied the first identity of Theorem 2.1 with n = d, i = 0, j = (d + 1) n+2 -2 -d. The identity

0 = U (d+1) n+2 -2-d U (d+1) n+1 -1 • T d+1 -U (d+1) n+2 -1 U (d+1) n+1 -2 • T d+1
is now the case (n, d) = ((d -1) n+1 , d + 1) of Lemma 3.5. 2

Proof of Theorem 1.4

Proof of Theorem 1.4 Equality holds for n = 0. Setting γ n = [0; 2x -1, 1 (, 2(x -1), 1

) n ] we have

γ n 1 -γ n = 0; 2x -2, 1 (, 2(x -1), 1) n-1
showing

γ n+1 = 1 2x -1 + 1 1+ γn 1-γn = 1 2x -γ n .
The result follows now by induction from the trivial identities

1 2x -Un U n+1 = U n+1 2xU n+1 -U n = U n+1 U n+2 .
2 An easy computation shows the continued fraction expansion

x -x 2 -1 = [0; 2x -1, 1, 2(x -1), 1, 2(x -1), 1, 2(x -1)].
for x ∈ {2, 3, 4, . . .}. Equality follows thus from analytic continuation whenever both sides make sense.

Combining Theorem 1.3 and Theorem 1.4 we see that

S n,d = 0; 2x -1, 1 (, 2(x -1), 1) (d+1) n+1 -2
(using a hopefully self-explanatory notation) is a convergent of x -√ x 2 -1 for x = 2, 3, . . ..

A sum of products of two binomial coefficients 4.1 Coefficients of Chebyshev polynomials

Lemma 4.1 Explicit expressions for coefficients of Chebyshev polynomials are given by the formulae

T n = 1 2 ⌊n/2⌋ k=0 (-1) k n + 1 -k k - n -1 -k k -2 (2x) n-2k , U n = ⌊n/2⌋ k=0 (-1) k n -k k (2x) n-2k (using the conventions -1 -2 = -1, =-1,-2 -2 = 0, -1 -1 = 1, =-1 -1 = 0). Proof
The formulae hold obviously for T 0 , T 1 and U 0 , U 1 . We have now

T n+1 = 2xT n -T n-1 = 2x 1 2 ⌊n/2⌋ k=0 (-1) k n + 1 -k k - n -1 -k k -2 (2x) n-2k - 1 2 ⌊(n-1)/2⌋ k=0 (-1) k n -k k - n -2 -k k -2 (2x) n-1-2k = 1 2 k (-1) k n + 1 -k k + n + 1 -k k -1 (2x) n+1-2k - 1 2 k (-1) k n -1 -k k -2 + n -1 -k k -3 (2x) n+1-2k = 1 2 k (-1) k n + 2 -k k - n -k k -2 (2x) n+1-2k
and

U n+1 = 2xU n -U n-1 = 2x ⌊n/2⌋ k=0 (-1) k n -k k (2x) n-2k - ⌊(n-1)/2⌋ k=0 (-1) k n -1 -k k (2x) n-1-2k = k (-1) k n -k k + n -k k -1 (2x) n+1-2k = k (-1) k n + 1 -k k (2x) n+1-2k .
These identities imply the result by induction. 2

A curious identity

Rewriting Chebyshev polynomials in terms of binomial coefficients using the identities of Lemma 4.1, some identities among Chebyshev polynomials are special cases of the following result.

Theorem 4.2 The expression

f (a, d, n) x = d-n k=0 a + d + x -k k d + k -x d -n -k is constant in x and depends only on a, d ∈ C and n ∈ d -N = {d, d -1, d - 2, d -3, . . .}.
Observe that all values f (a, d, n) x are determined by the values f (0, d, n) x using the trivial identity

f (a, d, n) x = f (a -2c, d + c, n + c) x+c (9) with c = a/2. Theorem 4.2 implies that Q N (z) = f (0, z/2, z/2 -N ) * is a polynomial in Q[z] of degree N such that Q N (Z) ⊂ Z. Lemma 4.3 We have the identities f (a, d, n) x = f (a -1, d, n) x + f (a -1, d, n + 1) x-1 (10)
and

f (a, d, n) x = f (a -1, d, n) x+1 + f (a -1, d, n + 1) x+1 (11)
Proof Follows from the computations

f (a, d, n) x = d-n k=0 a -1 + d + x -k k + a -1 + d + x -k k -1 d + k -x d -n -k = f (a -1, d, n) x + k a -1 + d + x -1 -(k -1) k -1 d + (k -1) -(x -1) d -(n + 1) -(k -1) = f (a -1, d, n) x + f (a -1, d, n + 1) x-1 and f (a, d, n) x = d-n k=0 a + d + x -k k d + k -x -1 d -n -k + d + k -x -1 d -n -1 -k = f (a -1, d, n) x+1 + f (a -1, d, n + 1) x+1 2 Proof of Theorem 4.2 Since x k = x(x-1)•••(x-k+1) k!
, the function f (a, d, n) x is a polynomial of degree at most d -n in x. It is thus independent of x for n = d. Subtracting equation ( 10) from ( 11) we get

f (a -1, d, n) x+1 -f (a -1, d, n) x = f (a -1, d, n + 1) x-1 -f (a -1, d, n + 1) x+1
which implies the result by induction on d -n. 2

4.3 A few properties of f (0, d, n)

The numbers

l i,j = f (0, (i -1)/2, j -(i + 1)/2) = i-j k=0 i-1 2 + x -k k i-1 2 + k -x i -j -k
with i ∈ N and j ∈ {0, . . . , i} (and x arbitrary) form the "Pascal-like" triangle: Proposition 4.4 We have l i,0 = (-1) i , l i,i = 1 and l i,j = l i-1,j-1 + l i-1,j .

1 -1 1 1 0 1 -1 1 1 1 1 0 2 2 1 -
Proof Using x = i-1 2 we get for j = 0 the evaluation

f 0, i -1 2 , - i + 1 2 = i k=0 i -1 -k k k i -k = -1 i i 0 = (-1) i . For i = j we get l i,i = f 0, i-1 2 , i-1 2 -i+1
Using (10) followed by two applications of ( 9) with c = -1 2 we have

l i,j = f 0, i -1 2 , j - i + 1 2 = f -1, i -1 2 , j - i + 1 2 + f -1, i -1 2 , j - i + 1 2 + 1 = f 0, i -1 2 - 1 2 , j - i + 1 2 - 1 2 + f 0, i -1 2 - 1 2 , j - i + 1 2 + 1 2 = f 0, (i -1) -1 2 , j -1 - (i -1) + 1 2 +f 0, (i -1) -1 2 , j - (i -1) + 1 2 = l i-1,j-1 + l i-1,j
which proves the result. 2

An LU-decomposition

Interpreting the integers l i,j , i, j ≥ 0 as the coefficients of an infinite unipotent matrix L and introducing similarly the matrix M with coefficients M i,j = l i+j,j , we have the following result:

Proposition 4.5 We have M = LU
where U is the upper-triangular matrix with coefficients U i,j = j i , i, j ≥ 0. In particular, we have det(M (n)) = 1 where M (n) is the square matrix consisting of the first n rows and columns of M . Proposition 4.5 is a special case of the following more general result: We associate two infinite matrices to an infinite sequence α 0 = 1, α 1 , α 2 , . . . in a commutative ring with 1 as follows:

The first matrix M (α) with coefficients M i,j indexed by i, j ∈ N is defined recursively by

M 0,0 = 1, M 0,j = 1, M i,0 = α i , M i,j = M i-1,j + M i,j-1 , i, j ≥ 1.
The coefficients M i,j for j > 0 are also given by the formula

M i,j = i k=0 k + j -1 k α i-k .
The second matrix is the unipotent lower-triangular matrix L(α) with lower triangular coefficients L i,j = M i-j,j , i ≥ j ≥ 0. It satisfies L i,j = L i-1,j + L i-1,j-1 for i, j ≥ 1.

Proposition 4.6 We have M (α) = L(α)U where M (α), L(α) are as above and where U is unipotent upper-triangular with coefficients U = j i given by binomial coefficients.

Proof

We have obviously M i,j = (LU ) i,j if i = 0 or j = 0. The remaining cases follow by induction on i + j from the equalities

= k L i,k U k,j = k L i,k U k,j-1 + k L i,k U k-1,j-1 = k L i,k U k,j-1 + k Li-1,k U k,j-1 = M i,j-1 + Mi-1,j-1 = M i,j-1 + M i-1,j = M i,j
where M = M (1, 1 + α 1 , 1 + α 1 + α 2 , 1 + α 1 + α 2 + α 3 , . . .), respectively L = L(1, 1 + α 1 , 1 + α 1 + α 2 , . . .), is obtained from M by removing its first row, respectively from L by removing its first row and column. 2

A few more identities

The following results show other similarities between l i,j and binomial coefficients:

Proposition 4.7 (i) We have for all n, k ∈ N the equality n k = l n,k + 2l n,k+1 .

(ii) We have for all n the identity

x n = (-1) n + (x + 1) n k=1 l n,k (x -1) k-1 .

For proving assertion (i), it is enough to check the equality for all n with k = 0, 1. The general case follows from the last equality in Proposition 4.4.

The second assertion holds for n = 0. We have now

(

  k-1 + l n-1,k )(x -1) k-1 = (x -1) (-1) n-1 + (x + 1) n-1 k=1 l n-1,k (x -1) k-1

= 1 by a trivial computation.

Acknowledgements I thank Bernard Parisse for a useful discussion.

* This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025). The author is a member of the project-team GALOIS supported by this LabEx.

+(-1) n-1 + (x + 1) n-1 k=1 l n-1,k (x -1) k-1 +(-1) n + (x + 1)(-1) n-1 -(x -1)(-1) n-1 -(-1) n-1 = (x -1)x n-1 + x n-1 = x n by induction. 2

A few integer sequences

A few integer sequences related to the numbers l i,j appear seemingly in [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] (proofs are probably easy in most cases). Observe that the array l i,j with its first row removed appears in [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF],

The sequence 1, 0, 2, 6, 22, 80, 296, 1106, . . . , l 2n,n , n = 0 of central coefficients coincides seemingly with A72547 of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF].

It is easy to show that the sequence 1, 0, 2, 2, 6, 10, 22, . . . , s n = n k=0 l n,k of row-sums is given by s

The closely related sequence 1 2 s n+1 coincides with A1045 of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]. 1, 1, 4, 8, 20, 44, 100, . . . , a n = n k=0 l n,k (k + 1) coincides with A84219 of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]. 0, 0, 1, 3, 9, 23, 57, 135, 313, 711, . . . , n k=2 l n,k (k -1) coincides (up to a shift of the index) with A45883 of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]. 1, 2, 6, 14, 34, 78, 178, . . . , n k=0 l n,k (2k+1) coincides seemingly with A59570 of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF].

There are certainly other sequences of [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] related to the numbers l i,j . Interestingly, the descriptions of the above sequences are linked to several different and apparently unrelated mathematical areas.