Chebyshev Polynomials are a family of orthogonal polynomials that pop up in all kinds of places in math, and they have a lot of quite interesting properties. One characterization of them is that they are the unique polynomials that satisfy
Tn(cos(x)) = cos(n*x).
Given an nonnegative integer
n, you should output the
n-th Chebyshev Polynomial.
n-th Chebyshev Polynomial is given by following three term recursion:
T0(x) = 1 T1(x) = x Tn+1(x) = 2*x*Tn(x) - Tn-1(x)
If your language has a native polynomial type, you can use that one as an output, otherwise you should output a list of coefficients in ascending- or descending order, or as a string representing a polynomial.
T0(x) = 1 T1(x) = x T2(x) = 2x^2 - 1 T3(x) = 4x^3 - 3 x T4(x) = 8x^4 - 8x^2 + 1 T5(x) = 16x^5 - 20x^3 + 5x T10(x) = 512x^10 - 1280x^8 + 1120x^6 - 400x^4 + 50x^2 - 1
In the descending degree list format we'd get
T3(x) = [4,0,-3,0] and in the ascending degree format we'd get
T3(x) = [0,-3,0,4]