Does $z ^k+ z^{-k}$ belong to $\Bbb Z[z + z^{-1}]$?

Let $z$ be a non-zero element of $\mathbb{C}$. Does $z^k + z^{-k}$ belong to $\mathbb{Z}[z + z^{-1}]$ for every positive integer $k$?

Motivation: I came up with this problem from the following question.

Maximal real subfield of $\mathbb{Q}(\zeta )$

-
$z^k+z^{-k}$ is a polynomial (with integer coeffiecients) of $z+z^{-1}$. In fact it is a Chebyshev polynomial of the second kind. – PAD Jul 25 '12 at 5:43
What's the reason for the downvotes? – Makoto Kato Jul 27 '12 at 6:05

Let's go by induction as in @Arturo Magidin's answer. The result holds for $k=0,1$. Assume $z^k+z^{-k} \in \mathbb{Z}[z+z^{-1}]$ for $0\le k\le n$. But $$z^{n+1}+z^{-(n+1)} = (z^n+z^{-n})(z+z^{-1}) - (z^{n-1} + z^{-(n-1)}),$$ and so $z^{n+1}+z^{-(n+1)} \in \mathbb{Z}[z+z^{-1}]$.

-
The result holds for $k=0,1$. – Alexander Thumm Jul 25 '12 at 5:26
@AlexanderThumm: I use $k=1,2$ as the base case. Arturo showed the result held for $k=2$ and I didn't repeat the argument. – user26872 Jul 25 '12 at 5:33
Yes I know. I only wanted to mention, that there would be no argument required if you would start with $k=0,1$. – Alexander Thumm Jul 25 '12 at 5:39
@AlexanderThumm: I admit, that is cleaner ... – user26872 Jul 25 '12 at 5:40
@AlexanderThumm: Edited. Thanks for the input. – user26872 Jul 25 '12 at 5:42

Yes. By the fundamental theorem of symmetric polynomials, $x^k+y^k\in\Bbb Z[x,y]^{S_2}$ can be written as a polynomial in $e_1=x+y$ and $e_2=xy$, say $P_k(e_1,e_2)$. Then we have

$$x^k+x^{-k}=P_k(x+x^{-1},1)\in\Bbb Z[x+x^{-1}].$$

We can of course interchange the formal variable $x$ with a specific nonzero complex number as we desire. In fact, this is the power sum $p_k(x,x^{-1})$, and the relationship between the power sums and elementary symmetric polynomials is given recursively by Newton's identities.

For a quick inductive proof of the fundamental theorem,

If $x_n|f$ then $x_1\cdots x_n|f$, and dividing out we are left with a symmetric polynomial of smaller degree than before. Otherwise, write $f(x_1,\cdots,x_{n-1},0)$ as a polynomial $p$ in the elementary symmetric polynomials $\hat{e}_i$ of the first $n-1$ variables, $p(\hat{e}_1,\cdots,\hat{e}_{n-1})$. Now the polynomial $$f(x_1,\cdots,x_n)-p(e_1,\cdots,e_{n-1})$$ is symmetric in all of $x_1,\cdots,x_n$ and evaluates to $0$ at $x_n=0$ ie is divisible by $x_n$. Induct.

which I wrote down here.

-
Can we avoid the theorem of symmetric polynomials? – Makoto Kato Jul 25 '12 at 4:55
@MakotoKato yes, as in Arturo's more straightforward answer. I have an affinity for symmetric polynomials though, so I wanted to grab at the chance to mention them. – anon Jul 25 '12 at 4:56
Symmetric polynomials are pretty great though. – Dylan Moreland Jul 25 '12 at 4:58
Great answer! +1 – Belgi Jul 25 '12 at 5:37

Yes. It holds for $k=1$; it also holds for $k=2$, since $$z^2+z^{-2} = (z+z^{-1})^2 - 2\in\mathbb{Z}[z+z^{-1}].$$ Assume that $z^k+z^{-k}$ lie in $\mathbb{Z}[z+z^{-1}]$ for $1\leq k\lt n$. Then, if $n$ is odd, we have: \begin{align*} z^n+z^{-n} &= (z+z^{-1})^n - \sum_{i=1}^{\lfloor n/2\rfloor}\binom{n}{i}(z^{n-i}z^{-i} + z^{i-n}z^{i})\\ &= (z+z^{-1})^n - \sum_{i=1}^{\lfloor n/2\rfloor}\binom{n}{i}(z^{n-2i}+z^{2i-n}). \end{align*} and if $n$ is even, we have: \begin{align*} z^n+z^{-n} &= (z+z^{-1})^n - \binom{n}{n/2} - \sum_{i=1}^{(n/2)-1}\binom{n}{i}(z^{n-i}z^{-i} + z^{i-n}z^{i})\\ &= (z+z^{-1})^n - \binom{n}{n/2} - \sum_{i=1}^{(n/2)-1}\binom{n}{i}(z^{n-2i}+z^{2i-n}). \end{align*} If $1\leq i\leq \lfloor \frac{n}{2}\rfloor$, then $0\leq n-2i \lt n$, so $z^{n-2i}+z^{2i-n}$ lies in $\mathbb{Z}[z+z^{-1}]$ by the induction hypothesis. Thus, $z^n+z^{-n}$ is a sum of terms in $\mathbb{Z}[z+z^{-1}]$.

-