<s>[INST] Proving that the sum of $n^{th}$ powers of the roots of a quadratic with integer coefficients is also an integer I am trying to prove that if a quadratic equation $x^2+px+q$ has roots $\alpha$ & $\beta$, then $$\alpha^n+\beta^n\in Z\ \text{for all }\ \ n\in N $$
My attempt:
$$\alpha^n+β^n=(α+β)^n-\sum_{k=1}^{n-1}\ {n\choose k} \ a^{n-k}\ b^k$$
For odd $n$:
$$\begin{aligned}
\sum_{k=1}^{n-1}\ {n\choose k} \ a^{n-k}\ b^k=&\ \ \ \ {n\choose 1}a^{n-1}b\quad +\quad{n\choose 2}a^{n-2}b^2 \quad\ \ \ ...\quad {n\choose \frac{n-1}{2}}a^{\frac{n+1}{2}}b^{\frac{n-1}{2}}\\
&\quad \quad \quad \quad \quad  \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad +\\
\\
&{n\choose n-1}a^{1}b^{n-1}+{n\choose n-2}a^{2}b^{n-2\quad}...{n\choose \ n- \frac{n-1}{2}}a^{\frac{n-1}{2}}b^{\frac{n+1}{2}}\\
\\
=& {n\choose 1}αβ\ (α^{n-2}+β^{n-2})+{n\choose 1}(αβ)^2\ (α^{n-4}+β^{n-4})...\\
\\
=& \sum_{k=1}^{\frac{n-1}{2}}{n\choose k}(αβ)^k\ (α^{n-2k}\ +\ β^{n-2k})
\end{aligned}$$
Defining $I_n:=α^n\ +\ β^n$, therefore, $$I_n=(-p)^n-\sum_{k=1}^{\frac{n-1}{2}} {n\choose k}\cdot q^k\cdot I_{n-2k}$$
Since $(-p)^n$, $q$ and $n\choose k$ are integers, $I_N$ is an integer if $I_n$ is an integer for all odd $n<N$
Base step:
$$\alpha+β=-p\ \Rightarrow integer$$
$$\alpha^3+β^3=(α+β)^3-3αβ(α+β)=\ -p^3+3pq\ \Rightarrow integer$$
Strong induction:
Assuming $I_n$ is an integer for all odd $n$ unto some odd natural number $k$,
$$I_{k+2}=(-p)^{K+2}-[{k+2\choose 1}\ q\ I_k\ +\ {k+2\choose 2}\ q^2\ I_{k-2}\ {k+2\choose 3}\ q^3\ I_{k-4}\ ...\ {k+2\choose \frac{k+1}{2}}\ q^{\frac{k+1}{2}}\ I_1]$$
$ I_{k+2} $ is also an integer. Since it has already been shown that $I_1$ and $I_3$ are integers, $I_n$ must be an integer for all odd natural numbers.
For even $n$:
Using a similar process, it can be shown that for even $n$,
$$\sum_{k=1}^{n-1}\ {n\choose k}\ α^{n-k}\ β^k=\ {n\choose \frac{n}{2}}\ (αβ)^{\frac{n}{2}}\ +\  \sum_{k=1}^{\frac{n}{2}-1}{n\choose k}(αβ)^k\ (α^{n-2k}\ +\ β^{n-2k})
$$
and thus$$I_n=(-p)^n-{n\choose \frac{n}{2}}\ (q)^{\frac{n}{2}}\ -\sum_{k=1}^{\frac{n-1}{2}} {n\choose k}\cdot q^k\cdot I_{n-2k}$$
Base step:
$$\alpha^2+β^2=(α+β)^2-2αβ=\ p^2-2q\ \Rightarrow integer$$
$$\alpha^4+β^4=(α+β)^4-4αβ(α^2+β^2)-6(αβ)^2 \Rightarrow integer$$
Strong induction:
Assuming $I_n$ is an integer for all even $n$ upto some even natural number $k$,
$$I_{k+2}=(-p)^{K+2}-{k+2\choose \frac{k+2}{2}}(p)^{\frac{K+2}{2}}\      -\ [{k+2\choose 1}\ q\ I_k\ +\ {k+2\choose 2}\ q^2\ I_{k-2}\ {k+2\choose 3}\ q^3\ I_{k-4}\ ...\ {k+2\choose \frac{k+1}{2}}\ q^{\frac{k+1}{2}}\ I_1]$$
$ I_{k+2} $ is also an integer. Since it has already been shown that $I_2$ and $I_4$ are integers, $I_n$ must be an integer for all even natural numbers.
Is this proof correct? Please point out anything that I have missed or should mention explicitly. Moreover, is there any way to prove the statement for both even and odd $n$ directly or is it necessary to deal with them separately?
 [/INST] Here is a "cheat" method. The Fundamental theorem of symmetric polynomials says that any symmetric polynomial $f(x,y)$ with integer coefficients (meaning $f(x,y)=f(y,x)$) can be written as an integer-coefficient polynomial of $xy$ and $x+y$ (the elementary symmetric polynomials.)
In your case, since $f(x,y)=x^n+y^n$ is a symmetric polynomial, it can be written as a polynomial $g(x+y,xy)$ with integer coeffcients. Now, we have $\alpha^n+\beta^n=g(\alpha+\beta,\alpha\beta)=g(-p,q)$, which is clearly an integer.
</s>