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

Question

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}$?

Answer 1

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}

Answer 2

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$.

Answer 3

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)

Answer 4

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}.$$