1
$\begingroup$

Consider the Chebyshev polynomials $T_n(x), n = 0, 1, \ldots$ which are recursively defined by $$T_0(x) = 1; \quad T_1(x) = x; \quad T_n(x) = 2x\cdot T_{n−1}(x) − T_{n−2}(x)$$ for $n = 2, 3, \ldots$. I need to show that

$$T_n(x) = 2^{n−1}\cdot (x − x_0)(x − x_1) . . . (x − x_{n−1})$$

I think I need to do this by induction, but am not entirely sure. Does anyone have some insight into this that would help me work through it?

I know I start with the $n = 1$ case, in which case, $T_n(x) = 2^0\cdot(x-x_0)$ (I think)

Then I am guessing I need to assume it works for $n$ cases, and prove for $n+1$?

Thanks!

  • 0
    What exactly are you trying to show? That the leading coefficient is $2^{n-1}$?2012-09-11
  • 0
    I think that is part of it but shouldnt the terms that follow have some significance?2012-09-11
  • 0
    Well, every polynomial of degree $n$ can be expressed as a constant times $\prod_{k=0}^{n-1} (x-x_k)$, so the only parameters are $n$, the constant and $x_0,...,x_{n-1}$. I am guessing that you are not computing the roots here, so that just leaves $n$ and the constant. You should be able to show that $T_n$ has degree $n$, and that the leading coefficient is $2^{n-1}$, for $n\geq 1$. Use induction.2012-09-11
  • 0
    Every polynomial with real can be factored in $\Bbb C$. So you can always write any polynomial as $(x-x_0)(x-x_1)\cdots(x-x_n)$ with $x_n \in \Bbb C$. So it really doesn't matter. All you have to show is that $T_{n+1}$ has roots in common with $T_n$ (assuming $x_0$ has the same value for $T_0, T_1, T_2, \ldots$.2012-09-11
  • 0
    @copper.hat So are you suggesting I say: T(n+1) = 2^n * (x-xo)(x-x1)...(x-x_n) I am not sure what follows from that2012-09-11
  • 0
    @EdGorcenski: I may be missing something, but I don't think the Chebychev roots are common between $T_n$ and $T_{n+1}$?2012-09-11
  • 0
    I guess I am just not entirely sure how the induction works in this case.2012-09-11
  • 0
    @copper.hat I don't think so either.2012-09-11
  • 0
    @SamuelGregory Assume that the hypothesis is true for $T_n$. Show that this assumption must lead to the hypothesis being true for $T_{n+1}$. Actually you might want to use strong induction, so assume that the hypothesis is true for all $m \le n$.2012-09-11
  • 0
    For n+1, don't we just have that: T(n+1) = 2^n * (x-xo)(x-x1)...(x-x_n) ?2012-09-11
  • 0
    @SamuelGregory Yes, but you also have the relation that $T_{n+1} = 2xT_n-T_{n-1}$, which you must show is equal to $T_{n+1} = 2^n(x-x_0)\cdots (x-x_n)$2012-09-11
  • 0
    In fact $T_n$ and $T_{n+1}$ are relatively prime as polynomials, i.e. they have no common polynomial factor of degree $\ge 1$. This is easy to show by induction.2012-09-12

1 Answers 1

4

It is straightforward to to see that the leading coefficient of $T_1$ is $2^0$, and the degree of $T_1$ is $1$.

So suppose the degree of $T_n$ is $n$, and the leading coefficient of $T_n$ is $2^{n-1}$. Then since $T_{n+1}(x) = 2 x T_n(x) - T_{n-1}(x)$, it is clear that the degree of $T_{n+1}$ is $n+1$ and the leading coefficient is $2 . 2^{n-1} = 2^{n}$. Hence it is true for all $n$.

Clarification: To see why $T_{n+1}$ has degree $n+1$, suppose for $k < n+1$ that $T_k$ has degree $k$, and leading coefficient $2^{k-1}$. Then $T_k$ will have the form $T_k(x) = 2^{k-1} x^k + \cdots$, where the $\cdots$ means a polynomial of degree $< k$. Then $T_{n+1}(x) = 2 x T_n(x) - T_{n-1}(x) = 2 x (2^{n-1} x^n + \cdots) - (2^{n-1} x^{n-1} + \cdots) = 2^{n} x^{n+1} + \cdots$. Hence $T_{n+1}$ has degree $n+1$ and leading coefficient $2^n$.

  • 1
    I like how this solution doesn't concern itself with the rest of the structure of the polynomials -- straight to the point.2012-09-11
  • 0
    I'm sorry, why is it clear that the degree of T_(n+1) is n+1?2012-09-11
  • 4
    @SamuelGregory $T_{n+1} = 2^{n-1}\color{#C00000}{2x}\color{#0000C0}{(x-x_0)(x-x_1)\cdots (x-x_n)}-T_{n-1}$. The red part is a polynomial of degree 1. The blue part is a polynomial of degree $n$. The black parts are irrelevant. The polynomials are multiplied together, leading to a polynomial of degree $n+1$.2012-09-11