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$.
BdMO National Higher Secondary 2007/5
Re: BdMO National Higher Secondary 2007/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
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
One one thing is neutral in the universe, that is $0$.
Re: BdMO National Higher Secondary 2007/5
What about the divisibility?
Re: BdMO National Higher Secondary 2007/5
It's also provable by strong induction.Ehsan wrote:What about the divisibility?
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.
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........