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?
Best Answer
It's a little bit easier. You know, that $\alpha+\beta=-p\in \mathbb Z$ and $\alpha\beta=q\in \mathbb Z$. Observe, that $\alpha^n+\beta^n\in\{2,-p\}\subset \mathbb Z$ for $n\in \{0,1\}$. Hence for $n\geq 2$, we have \begin{align} \alpha^{n}+\beta^{n}&=(\alpha+\beta)(\alpha^{n-1}+\beta^{n-1})-\alpha\beta(\alpha^{n-2}+\beta^{n-2})\\&=-p(\alpha^{n-1}+\beta^{n-1})-q(\alpha^{n-2}+\beta^{n-2})\in \mathbb Z \end{align}