BdMO Online Forum

Problem 5:
If $x_1, x_2$ are the zeros of the polynomial $x^2-6x+1$, then prove that for every nonnegative integer $n$, $x_1^n+x_2^n$ is an integer and not divisible by $5$.

Note that $x_1+x_2=6,x_1x_2=1,$we use strong induction on $n$
Trivial for $n=1$,so let $x_1^{n-1}+x_2^{n-1},x_1^n+x_2^n$ is integer,then note that $(x_1+x_2)(x_1^n+x_2^n)=x_1^{n+1}+x_2^{n+1}+x_1x_2(x_1^{n-1}+x_2^{n-1}),$this equation easily implies that our induction is complete

What about the divisibility?

Ehsan wrote:What about the divisibility?

It's also provable by strong induction.
The base case is true.
Assume that $x_1^n+x_2^n$ and $x_1^{n-1}+x_2^{n-1}$
both are not divisible by 5.
$(x_1+x_2)(x_1^n+x_2^n)=x_1^{n+1}+x_2^{n+1}+x_1x_2(x_1^{n-1}+x_2^{n-1})$
$x_1+x_2=6, x_1x_2=1$
thus
$(x_1+x_2)(x_1^n+x_2^n)-x_1x_2(x_1^{n-1}+x_2^{n-1})=x_1^{n+1}+x_2^{n+1}$
$\Rightarrow 6(x_1^n+x_2^n)-(x_1^{n-1}+x_2^{n-1})=x_1^{n+1}+x_2^{n+1}$
here left side is not divisible by 5. so for all $n\in\mathbb{N}$ ,$ ,x_1^n+x_2^n$ is not divisible by 5.