$$T_n(x) = \frac{n}{2} \sum_{r=0}^{\lfloor \frac{n}{2} \rfloor} \frac{(-1)^r}{n-r} \binom{n-r}{r} (2x)^{n-2r}$$

Searching on the web yielded no results, and the result is given without proof on OEIS and Wolfram MathWorld

  • $\begingroup$ I have in my pre-thesis. $\endgroup$
    – Bob Dobbs
    Jan 25 at 9:22

2 Answers 2


It is defined by $T_n(x)=\frac{u^{n}+u^{-n}}{2}$ where $x=\frac{u+u^{-1}}{2}.$ This implies that $T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$. So, it is essentially enough to check this recursive relation at $n+1-2r$-the power term: $$\frac{n+1}{2}\frac{(-1)^r}{n+1-r}{n+1-r\choose r}2^{n+1-2r}=2\frac{n}{2}\frac{(-1)^{r}}{n-r}{n-r\choose r}2^{n-2r}-\frac{n-1}{2}\frac{(-1)^{r-1}}{n-r}{n-r\choose r-1}2^{n+1-2r}$$ which is equivalent to $$\frac{n+1}{n+1-r}{n+1-r\choose r}=\frac{n}{n-r}{n-r\choose r}+\frac{n-1}{n-r}{n-r\choose r-1}$$ and it is true.


Starting from the OGF

$$\sum_{n\ge 0} T_n(x) t^n = \frac{1-tx}{1-2tx+t^2}$$

We extract coefficients $[x^q] [t^n]$ where $0\le q\le n$. First do the coefficient on $q=0$ which is $[t^n] \frac{1}{1+t^2}.$ Continue with $q\ge 1$

$$[x^q] [t^n] \frac{1-tx}{1-2tx+t^2} = [x^q] [t^n] \frac{1-tx}{1+t^2} \frac{1}{1-2tx/(1+t^2)} \\ = [t^n] \frac{1}{1+t^2} \frac{2^q t^q}{(1+t^2)^q} - [t^n] \frac{1}{1+t^2} \frac{2^{q-1} t^{q}}{(1+t^2)^{q-1}} \\ = [t^n] \frac{2^q t^q}{(1+t^2)^{q+1}} - [t^n] \frac{2^{q-1} t^{q}}{(1+t^2)^{q}}.$$

Now we see here that $q$ and $n$ must have the same parity. Supposing that is true we obtain

$$2^q [t^{n-q}] \frac{1}{(1+t^2)^{q+1}} - 2^{q-1} [t^{n-q}] \frac{1}{(1+t^2)^q} \\ = 2^q (-1)^{(n-q)/2} {(n-q)/2+q\choose q} - 2^{q-1} (-1)^{(n-q)/2} {(n-q)/2+q-1\choose q-1} \\ = 2^q (-1)^{(n-q)/2} {(n+q)/2\choose q} - 2^{q-1} (-1)^{(n-q)/2} \frac{q}{(n+q)/2} {(n+q)/2\choose q} \\ = \frac{n}{n+q} 2^q (-1)^{(n-q)/2} {(n+q)/2\choose q}.$$

Note that this also gives the correct value for $q=0$ so we can merge that case into our formula. Observe also that we get zero from the binomial coefficient when $(n+q)/2\lt q$ or $n\lt q.$

Now when $q$ and $n$ have the same parity with $n$ and $q$ non-negative then $n-q=2r$ where $0\le r\le \lfloor n/2 \rfloor.$ We have $q=n-2r$ and obtain summing over $r$

$$\sum_{r=0}^{\lfloor n/2 \rfloor} x^{n-2r} \frac{n}{2n-2r} 2^{n-2r} (-1)^r {n-r\choose n-2r} \\ = \frac{n}{2} \sum_{r=0}^{\lfloor n/2 \rfloor} (2x)^{n-2r} \frac{(-1)^r}{n-r} {n-r\choose r}.$$

This is the claim.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .