# How to write $x^m+x^{-m}$ as a polynomial in $x+x^{-1}$.

I did find this question Proving that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$. but it only shows by induction that this is possible, not the actual form of the solution. How, for example, would you write $$x^2+x^{-2}$$ in a polynomial of $$x+x^{-1}$$?

• Did you mean $x^2\color{red}+x^{-2}$? Because in that case it's $(x+x^{-1})^2-2$ Oct 25, 2019 at 4:18
• Yes I did, edited. How did you come up with that? Just from squaring $(x+x^-1)$ and subtracting off the extra $2$, or is there a more general way? Oct 25, 2019 at 4:21
• This answer math.stackexchange.com/a/1341510/42969 to the referenced question shows the explicit solution. Oct 25, 2019 at 4:34

It's just a simple system of equations (simple, if the degree is low...)

You want \begin{align} x^2+\frac1{x^2}&=a+b\left(x+\frac1x\right)+c\left(x+\frac1x\right)^2\\ &=a+2c+bx+\frac bx+cx^2+\frac c{x^2}. \end{align} And you see by inspection that $$a+2c=1$$, $$b=0$$, $$c=1$$. So $$a=-2$$. That is \begin{align} x^2+\frac1{x^2}&=-2+\left(x+\frac1x\right)^2\\ \end{align}

• Thanks, I will mark this as the accepted answer since it does generalize for $m>2$. I see it is very simple now, but thank you for the clear explanation. Oct 25, 2019 at 4:27

These are basically Chebyshev polynomials. One can derive an explicit formula for them via generating functions.

Let $$y=x+x^{-1}$$ and consider the formal power series $$F(x,t)=\sum_{n=0}^\infty(x^n+x^{-n})t^n.$$ Then \begin{align} F(x,t)&=\sum_{n=0}^\infty x^nt^n+\sum_{n=0}^\infty x^{-n}t^n =\frac1{1-xt}+\frac1{1-x^{-1}t}=\frac{(1-xt)+(1-x^{-1}t)}{(1-xt)(1-x^{-1}t)}\\ &=\frac{2-(x+x^{-1})t}{1-(x+x^{-1})t+t^2}=\frac{2-yt}{1-yt+t^2}=(2-yt) \frac1{1-(y-t)t}\\ &=(2-yt)\sum_{m=0}^\infty(y-t)^mt^m=(2-yt)\sum_{m=0}^n\sum_{k=0}^{m} (-1)^k\binom{m}{k}y^{m-k}t^{m+k}\\ &=(2-yt)\sum_{m=0}^\infty(y-t)^mt^m=(2-yt)\sum_{n=0}^\infty t^n\sum_{k:0\le k\le n/2}(-1)^k\binom{n-k}{k}y^{n-2k}. \end{align} Comparing coefficients of $$t^n$$ gives $$x^n+x^{-n}=2\sum_{k:0\le k\le n/2}(-1)^k\binom{n-k}{k}y^{n-2k} -\sum_{k:0\le k\le (n-1)/2}(-1)^k\binom{n-1-k}{k}y^{n-2k}.$$ One can simplify this a bit: $$2\binom{n-k}{k}-\binom{n-1-k}{k}=\binom{n-k}{k}+\binom{n-k-1}{k-1} =\binom{n-k}{k}+\frac{k}{n-k}\binom{n-k}{k}$$ to get $$x^n+x^{-n}=\sum_{k:0\le k\le n/2}(-1)^k\frac{n}{n-k} \binom{n-k}{k}(x+x^{-1})^{n-2k}.$$

• Very interesting. I have not studied formal power series in more than one variable before. Oct 25, 2019 at 6:26

In order to get $$x^2$$ and $$x^{-2}$$ terms, square $$(x+x^{-1}$$). The result is $$x^2+2+x^{-2}$$.

So subtract $$2$$ to get what you want: $$x^2+x^{-2}=(x+x^{-1})^2-2$$.

• Thanks, does this generalize to $x^m+x^{-m}$ for $m>2$? Oct 25, 2019 at 4:25
• $(x+x^{-1})^3=x^3+3x+3x^{-1}+x^{-3}$ so $x^3+x^{-3}=(x+x^{-1})^3-3(x+x^{-1})$ Oct 25, 2019 at 4:30
• $(x+x^{-1})^4=x^4+4x^2+6+4x^{-2}+x^{-4}$ so $x^4+x^{-4}=(x+x^{-1})^4-4(x^2+x^{-2})-6=(x+x^{-1})^4-4(x+x^{-1})^2+2$ Oct 25, 2019 at 4:35
• I get the point, you can stop now :) Oct 25, 2019 at 4:39
• :), okay, thanks, will do Oct 25, 2019 at 4:39

The inductive argument does tell you how to do this - and, it's worthwhile to see that induction very often gives you the answers you are after, especially since the fact that inductive proofs can be unrolled is often overlooked.

In the linked answer, it is noted that $$x^{k+1}+x^{-k-1} = (x^k +x^{-k})(x+x^{-1}) - (x^{k-1} + x^{-k+1}).$$ and an inductive argument is built from this, but remember that the inductive hypothesis is just that, for each $$k$$, there exists some polynomial $$P_k$$ such that $$P_k(x+x^{-1})= x^k+x^{-k}$$. If we fill out the proof more completely, the implication here is that $$x^{k+1}+x^{-k-1} = P_k(x+x^{-1})\cdot (x+x^{-1}) - P_{k-1}(x+x^{-1}).$$ And then we see that the left hand side is a polynomial in $$x+x^{-1}$$ as well - but we can be more explicit: Let $$P_{k+1}(z)=zP_k(z)-P_{k-1}(z)$$ where we start the sequence as $$P_0(z)=2$$ and $$P_1(z)=z$$. Then, we have $$P_k(x+x^{-1})=x^k+x^{-k}$$ due to the inductive argument. Note that this sequence is very easy to compute incrementally: $$P_2(z)=z\cdot P_1(z) - P_0(z) = z^2 - 2$$ $$P_3(z)=z\cdot P_2(z) - P_1(z) = z^3 - 3z$$ $$P_4(z)=z\cdot P_3(z) - P_2(z) = z^4 - 4z^2 + 2$$ and so on.

As pointed out in the comments, it is possible to write these terms in a general form, although it's a bit surprising that the form you get is actually a polynomial. I won't go into details, since I'm using the usual tools for solving linear homogenous recurrences:

$$P_k(z) = \frac{\left(z - \sqrt{z^2-4}\right)^k + \left(z + \sqrt{z^2-4}\right)^k}{2^k}$$

Note that the $$\sqrt{z^2-4}$$ terms cancel out due to the symmetry of the sum and this does always leave a polynomial.

(I also think this sequence has a name, but I don't know what it is)

• It might be worthwhile to expand this to actually obtain an explicit formula, which should be easy to do since we already have the recurrence (using e.g. generating functions). Oct 25, 2019 at 4:37
• That is very interesting. I have not thought to do this before. I will have to keep it in mind, thanks! Oct 25, 2019 at 4:41
• @YiFan Thanks, I added it, I'd thought that the explicit formula was a bit worse than it is when I was writing this. Oct 25, 2019 at 4:43