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