[Question]
  [
[Chebyshev Polynomials](https://en.wikipedia.org/wiki/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(nx)\$.
### 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:
$$\begin{align}
T\_0(x) & = 1 \\
T\_1(x) & = x \\
T\_{n+1}(x) & = 2xT\_n(x) - T\_{n-1}(x)
\end{align}$$
![](https://upload.wikimedia.org/wikipedia/commons/e/eb/Chebyshev_Polynomials_of_the_1st_Kind_%28n%3D0-5%2C_x%3D%28-1%2C1%29%29.svg)
### 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.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the shortest code in bytes wins
### Examples
```
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]`
  
[Answer]
# Mathematica, 15 bytes
```
#~ChebyshevT~x&
```
Of course, Mathematica has a builtin.
If an alternative input form is allowed (10 bytes):
```
ChebyshevT
```
takes an integer `n` and a variable.
[Answer]
# [Octave](https://www.gnu.org/software/octave/), 39 bytes
```
@(n)round(2^n/2*poly(cos((.5:n)/n*pi)))
```
[Try it online!](https://tio.run/##y08uSSxL/Z9mq6en999BI0@zKL80L0XDKC5P30irID@nUiM5v1hDQ8/UKk9TP0@rIFNTU/N/SmZxgUaahoGmJheUaYhgGiGYpkgKgIr/AwA "Octave – Try It Online")
### Explanation
`cos((.5:n)/n*pi)` builds a vector with the [roots of the polynomial](https://en.wikipedia.org/wiki/Chebyshev_polynomials), given by
[![enter image description here](https://i.stack.imgur.com/Qtf0Y.png)](https://i.stack.imgur.com/Qtf0Y.png)
`poly` gives the monic polynomial with those roots. Multiplying by `2^n/2` scales the coefficients as required. `round` makes sure that results are integer in spite of numerical precision.
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 12 bytes
Yes, a builtin. Shorter than Mathematica.
```
polchebyshev
```
[Try it online!](https://tio.run/##K0gsytRNL/ifpmCr8L8gPyc5IzWpsjgjtex/Wn6RRh5Q1EBHwRCIC4oy80qAAkoKunZAIk0jT1NT8z8A "Pari/GP – Try It Online")
---
Without builtin:
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 34 bytes
```
f(n)=if(n<2,x^n,2*x*f(n-1)-f(n-2))
```
[Try it online!](https://tio.run/##K0gsytRNL/j/P00jT9M2E0jaGOlUxOXpGGlVaAF5uoaauiDKSFPzf1p@kUaegq2CgY6CIRAXFGXmlQAFlBR07YAEyACgIgA "Pari/GP – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 62 bytes
```
t n|n<2=1:[0|n>0]|x<-(*2)<$>t(n-1)++[0]=zipWith(-)x$0:0:t(n-2)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/v0QhrybPxsjW0CraoCbPziC2psJGV0PLSNNGxa5EI0/XUFNbO9og1rYqsyA8syRDQ1ezQsXAysAKJGek@T83MTPPtqAoM69EQaNEwVTzPwA "Haskell – Try It Online")
flawr saved a byte.
[Answer]
## CJam (21 bytes)
```
1a2,qi{0X$+2f*@.-}*;`
```
This is a full program: the equivalent as an anonymous block is the same length:
```
{1a2,@{0X$+2f*@.-}*;}
```
[Online demo](http://cjam.aditsu.net/#code=1a2%2C%7B0X%24%2B2f*%40.-%7Dqi*%3B%60&input=5)
[Answer]
# Python + [SymPy](http://docs.sympy.org/latest/index.html), 66 bytes
```
from sympy.abc import*
T=lambda n:n<2and x**n or 2*x*T(n-1)-T(n-2)
```
[Try it online!](https://tio.run/##FcjBDoIwDADQs3xFj2sjRuaNyF/sB4qINGHdUnZgXz/19JKXa9mSPlpbLUU4asz1xvMLJOZkhbow7RznhUFHfXrWBU4ihWTg6aTgtB@w/@Oxrb8VEAVj/bzdcMexu2QTLU6uEJwgti8)
### With descending coefficients representation
```
from sympy import*
x=symbols('x')
T=lambda n:n<2and x**n or expand(2*x*T(n-1)-T(n-2))
```
[Try it online!](https://tio.run/##FYpBDoMgEADP5RV7c5doUunN1F/wAYzabiILQQ7wekpPk8lMrPkb5NXamYKHu/pYgX0MKWtV1u5buG4cykDKrpfz2@5AFnkbJzsUrQVCgqPErmh00RZlmmn6wxC1s1cGFkhOPgfOT1rUIyaWjDyCRe7PDw)
[Answer]
# [MATL](https://github.com/lmendo/MATL), 17 bytes
```
lFTi:"0yhEbFFh-]x
```
Coefficients are output in increasing order of degree.
[Try it online!](https://tio.run/##y00syfn/P8ctJNNKyaAywzXJzS1DN7bi/39DAwA "MATL – Try It Online") Or [verify all test cases](https://tio.run/##y00syfmf8D/HLSTTSsmgMsM1yc0tQze24r9LyH8DLkMuIy5jLhMuUy5DAwA).
## Explanation
For input *n*, the code applies the recursive relation *n* times. The two most recent polynomials are always kept on the stack. When a new polynomial is computed, the oldest is removed.
At the end, the second-last polynomial is displayed (the last polynomial is deleted), as we have done one too many iterations.
```
l        % Push 1
FT       % Push [0 1]. These are the first two polynomials
i:"      % Input n. Do the following n times
  0      %   Push 0
  y      %   Duplicate most recent polynomial
  h      %   Concatenate: prepends 0 to that polynomial
  E      %   Multiply coefficients by 2
  b      %   Bubble up. This moves second-most recent polynomial to top
  FF     %   Push [0 0]
  h      %   Concatenate: appends [0 0] to that polynomial
  -      %   Subtract coefficients
]        % End
x        % Delete. Implicitly display
```
[Answer]
## SageMath, 25 bytes
```
lambda n:chebyshev_T(n,x)
```
[Try it online](http://sagecell.sagemath.org/?z=eJzLScxNSklUyLNKzkhNqizOSC2LD9HI06nQBAB5EgkB&lang=sage)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 18 bytes
```
Cr1µ’ßḤ0;_’’$ß$µỊ?
```
[Try it online!](https://tio.run/##y0rNyan8/9@5yPDQ1kcNMw/Pf7hjiYF1PJAJRCqH56sc2vpwd5f9////TQE)
Returns a list of coefficients in ascending order.
There is another solution for **17 bytes** with floating-point inaccuracies.
```
RḤ’÷Ḥ-*ḞÆṛæ«’µ1Ṡ?
```
[Try it online!](https://tio.run/##y0rNyan8/z/o4Y4ljxpmHt4OpHW1Hu6Yd7jt4c7Zh5cdWg0UPbTV8OHOBfb///83BQA)
## Explanation
```
Cr1µ’ßḤ0;_’’$ß$µỊ?  Input: integer n
                Ị   Insignificant - abs(n) <= 1
                    If true, n = 0 or n = 1
   µ                  Monadic chain
C                       Complement, 1-x
 r1                     Range to 1
                    Else
               µ      Monadic chain
    ’                   Decrement
     ß                  Call itself recursively
      Ḥ                 Double
       0;               Prepend 0
         _              Subtract with
            $             Monadic chain
          ’’                Decrement twice
              $           Monadic chain
             ß              Call itself recursively
```
[Answer]
# [J](http://jsoftware.com/), 33 bytes
```
(0>.<:)2&*1:p.@;9:o._1^+:%~1+2*i.
```
[Try it online!](https://tio.run/##y/r/P03B1kpBw8BOz8ZK00hNy9CqQM/B2tIqXy/eME7bSrXOUNtIK1OPiys1OSNfQcM6TVPNTsFAwVDBSMFYwUTBVMHQ4P9/AA)
Assumes that floating-point inaccuracies are acceptable and creates the emoji `(0>.<:)`
For **41 bytes**, there is another solution that avoids floats.
```
(0&,1:)`(-&2((-,&0 0)~2*0&,)&$:<:)@.(>&1)
```
[Try it online!](https://tio.run/##DcgxCoAwDAXQvaf4g4RErCRVl6jFowhiERdv4NWrb3x3rQWrg5U6c9k5UmKOHSlU3tT@LdT44rL1nMkkhPO4HvBchDIUhoQBIyaY1voB)
[Answer]
# Ruby + [polynomial](http://adrianomitre.github.io/Polynomial/website/index.html), ~~59~~ 58+13 = ~~72~~ 71 bytes
Uses the `-rpolynomial` flag.
```
f=->n{x=Polynomial.new 0,1;n<2?[1,x][n]:2*x*f[n-1]-f[n-2]}
```
[Answer]
# [Python 2](https://docs.python.org/2/), 79 bytes
```
f=lambda n:n>1and[2*a-b for a,b in zip([0]+f(n-1),f(n-2)+[0,0])]or range(1-n,2)
```
[Try it online!](https://tio.run/##LYtBCsMgEADP7Sv26DYrqMdA@xHxsJLaLrQbkVzSz9sIOQ0MM3Xf3quG3sv9w9@8MOisD8@6xHBjm6GsDZgyiMJPqokuTcWo9UgDAafoyCVMR9ZYX0/jrVLAPj4Z12k9ztdLbaIbCEExgv0P "Python 2 – Try It Online")
[Answer]
# Axiom, 40 bytes
```
f(n,x)==(n<2=>x^n;2*x*f(n-1,x)-f(n-2,x))
```
results
```
(9) -> for i in [0,1,2,3,4,5,10] repeat output ["f(y)",i,"=", f(i,y)]
   ["f(y)",0,"=",1]
   ["f(y)",1,"=",y]
                   2
   ["f(y)",2,"=",2y  - 1]
                   3
   ["f(y)",3,"=",4y  - 3y]
                   4     2
   ["f(y)",4,"=",8y  - 8y  + 1]
                    5      3
   ["f(y)",5,"=",16y  - 20y  + 5y]
                      10        8        6       4      2
   ["f(y)",10,"=",512y   - 1280y  + 1120y  - 400y  + 50y  - 1]
                                                               Type: Void
```
it is possible define one substitution law for formula in Axiom use above f() function
for expansion of cos(n\*x) where n is one integer
```
(9) -> o:=rule cos(n*%y)==f(n,cos(%y))
   (9)  cos(%y n) == 'f(n,cos(%y))
                    Type: RewriteRule(Integer,Integer,Expression Integer)
                                                              Time: 0 sec
(10) -> b:=o cos(20*x)
   (10)
                 20                18                16                14
     524288cos(x)   - 2621440cos(x)   + 5570560cos(x)   - 6553600cos(x)
   +
                  12                10               8              6
     4659200cos(x)   - 2050048cos(x)   + 549120cos(x)  - 84480cos(x)
   +
               4            2
     6600cos(x)  - 200cos(x)  + 1
                                                 Type: Expression Integer
                       Time: 0.48 (EV) + 0.02 (OT) + 0.10 (GC) = 0.60 sec
```
[Answer]
# [C# (.NET Core)](https://www.microsoft.com/net/core/platform), 126 bytes
```
f=n=>n==0?new[]{1}:n==1?new[]{0,1}:new[]{0}.Concat(f(n-1)).Select((a,i)=>2*a-(i<n-1?f(n-2)[i]:0)).ToArray();
```
Byte count also includes:
```
using System.Linq;
```
[Try it online!](https://tio.run/##bZBRT8IwEMff@ylOnlqFZUN9YWyEGHkREyMmPhAemnKTJqPDthMJ2Wef7UaQRf8PTe/u17v/VZiBKDTWpZHqAxYHY3EbzKX6jAlRfItmxwWe8uRIwEnk3BiYNvc242Ust1LAVyHX8Mylouxc@oW8ZqUSY6lsH9yxXKWQQQKqzPO4zhKVpCpJwonC/XJ1jKqRi6JTFPZ93F6r4KFQgluaUTWIGAsWmKOwlPK@ZEk6vOYDKseuNPHAkC3lahQ67K2Yas0PlMX1pSdjtV9fql1p447b/UbmCJQ2JWfUjTVFjsEr8rX7JqSMwVXrn3Uedpf2ylwTG7xwbbBt1/iZS2MpC2aFfuRiQ78hSc9D3rW06FI30IMeY/Gflh2wtdOFKvIf7s0/4eESbsGKVHVIIjIkt@SO3JMo/AE "C# (.NET Core) – Try It Online")
The function returns polynomial as an array of coefficients in ascending order (from `x^0` to `x^n`)
Explanation:
```
f = n =>                          // Create a function taking one parameter (int)
    n == 0 ? new[] { 1 } :        // If it's 0, return collection [1]
    n == 1 ? new[] { 0, 1 } :     // If it's 1, return collection [0,1] (so x + 0)
    new[] { 0 }                   // Else create new collection, starting with 0
        .Concat(f(n - 1))         // Concatenate with f(n-1), effectively multiplying polynomial by x
        .Select((a, i) => 2 * a - (i < n - 1 ? f(n - 2)[i] : 0))
                                  // Multiply everything by 2 and if possible, subtract f(n-2)
        .ToArray();               // Change collection to array so we have a nice short [] operator
                                  // Actually omitting this and using .ElementAt(i) is the same length, but this is my personal preference
```
[Answer]
## JavaScript (ES6), 65 bytes
```
f=n=>n?n>1?[0,...f(n-1)].map((e,i)=>e+e-(f(n-2)[i]||0)):[0,1]:[1]
```
Inefficient for large `n`. Interesting but sadly also inefficient:
```
n=>[...Array(n+1)].map(g=(m=n,i)=>i<0|i>m?0:m<2?i^m^1:g(m-1,i-1)*2-g(m-2,i))
```
Very efficient for 68 bytes:
```
f=(n,a=[1],b=[0,1])=>n?f(n-1,b,[0,...b].map((e,i)=>e+e-(a[i]||0))):a
```
Returns an array of coefficients in ascending order.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 19 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
╛5%Ö←Äⁿ¿æ╔Dë!é╔J╗yì
```
[Run and debug it](https://staxlang.xyz/#p=be3525991b8efca891c944892182c94abb798d&i=0%0A1%0A2%0A3%0A4%0A5%0A10&m=2)
zipping takes a lot of bytes.
]