26

0

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 `T`

. _{n}(cos(x)) = cos(n*x)

### Challenge

Given an nonnegative integer `n`

, you should output the `n`

-th Chebyshev Polynomial. `T`

._{n}(x)

### Definition

The `n`

-th Chebyshev Polynomial is given by following three term recursion:

`T`_{0}(x) = 1
T_{1}(x) = x
T_{n+1}(x) = 2*x*T_{n}(x) - T_{n-1}(x)

### Details

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.

### Examples

`T`_{0}(x) = 1
T_{1}(x) = x
T_{2}(x) = 2x^2 - 1
T_{3}(x) = 4x^3 - 3 x
T_{4}(x) = 8x^4 - 8x^2 + 1
T_{5}(x) = 16x^5 - 20x^3 + 5x
T_{10}(x) = 512x^10 - 1280x^8 + 1120x^6 - 400x^4 + 50x^2 - 1

In the descending degree list format we'd get `T`

and in the ascending degree format we'd get _{3}(x) = [4,0,-3,0]`T`

_{3}(x) = [0,-3,0,4]

If I output a list, can I output

`0 1`

(i.e.`0*x+1`

) for`T_0`

? – Luis Mendo – 2017-08-10T20:07:24.217As long the order of the monomials is consistent that is ok! – flawr – 2017-08-10T20:08:51.690

@flawr is

`2*x*(2*x**2 - 1) - x`

ok as output for 3 for polynom supportive lang, or do we need the representation as desc coeffs? – Uriel – 2017-08-10T20:36:30.323Ah I unfortunately did not specify that further, so I guess that is ok, as it represents a polynomial. – flawr – 2017-08-10T20:37:54.247

11Meta discussion on the topic of English titles – Mego – 2017-08-10T21:03:54.250

3Are floating-point inaccuracies acceptable? i.e.

`T_5(n) = [0, 5, 3.55271e-15, -20, 0, 16]`

– miles – 2017-08-10T21:24:42.553@miles Yes that should be ok! – flawr – 2017-08-11T10:21:27.847

Is outputting a list of coefficients, but skipping the ones that are zero because the polynomial is odd/even okay? – proud haskeller – 2017-08-11T20:13:09.317

No I think that this should not be allowed, as that way you cannot determine the actual polynomial by the output alone without any additional information. – flawr – 2017-08-11T20:33:18.997

Maybe it’s good to add example outputs in “ascending coefficient list” format and “descending coefficient list” format for at least one of the polynomials – Lynn – 2017-08-11T23:41:55.260

@Lynn thanks, added! – flawr – 2017-08-12T08:12:54.530