CHEBYSHEV TRIANGLE


You probably know the Pascal triangle, of the binomial coefficients. I draw it here for later reference. Let B(i,j) denote the j-th element of the i-th row; the index i runs from 0 on, and j goes from 0 to i. For example B(3,2) = 3. 

                    1
                 1     1
              1     2     1
           1     3     3     1
        1     4     6     4     1
     ...

Let's draw another triangle, with 1 on the left side and 2 on the right side, 
                    2
                 1     2
              1     3     2
           1     4     5     2
        1     5     9     7     2
     1     6    14    16     9     2
  ...
If A(i,j) denotes the element in position j on the i-th row, then A(i,j) = A(i-1,j-1) + A(i-1,j).
Let's define T(i,j)=(-)j 2i-j-1 A(i,j). These are the numbers of the original triangle multiplied by a power of 2, namely 1/2 the uppermost right diagonal, 1 the one beneath it, 2 the next one, and so on. Furthermore the numbers are now alternating in sign. The triangle of the T's is 
                   1
                1    -1
             2    -3     1
          4    -8     5    -1
       8   -20    18    -7     1
    ...
Prove the following: cos(n x) = Sumk=0,.. n/2 T(n-k,k) cosn-2k(x)
For example, 
  cos(3x) = T(3,0) cos3(x) + T(2,1) cos(x)
          = 4 cos3(x) -3 cos(x)
  cos(4x) = T(4,0) cos4(x) + T(3,1) cos2(x) + T(2,2)
          = 8 cos4(x) - 8 cos2(x) + 1
The claim explains why i called the triangle after Chebyshev. The polynomial expansions of cos(nx) in terms of powers of cos(x) are called Chebyshev polynomials of first kind, cos(n x)=Tn( cos(x) ). These Chebyshev polynomials are defined by the recurrence relation T(n+1)(x) = 2 x Tn(x) - Tn-1(x), with T0(x)=1 and T1(x)=x.

What about the Chebyshev polynomials of second kind? Let's go back to Pascal triangle and define D(i,j) = (-)i+j 2j B(i,j). 

                    1
                -1     2
              1    -4     4
          -1     6   -12     8
        1    -8    24   -32    16
     ...
Next consider the polynomials (the sum runs over the k such that n+k is even) 
   Un(x) = Sumk D((n+k)/2, k) xk
For example, 
  U1(x) = D(1,1) x1 = 2 x
  U2(x) = D(1,0) x0 + D(2,2) x2 = -1 + 4 x2.
  U3(x) = D(2,1) x1 + D(3,3) x3 = -4 x + 8 x3.
Prove that sin((n+1)x) = sin(x) Un( cos(x) ).

By the way, Pascal triangle is related to Fibonacci numbers. Write the triangle left-aligned, 

    1
    1   1
    1   2   1
    1   3   3   1
    1   4   6   4   1
    ...
The sum of the diagonals are the Fibonacci numbers: 1, 1, 2, 3, 5, ... If you do the same for the Chebyshev triangle you get the Lucas numbers: 2, 1, 3, 4, 7, ...

Marco Corvi - 2005