BdMO National Higher Secondary 2007/5

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
BdMO
Posts:134
Joined:Tue Jan 18, 2011 1:31 pm
BdMO National Higher Secondary 2007/5

Unread post by BdMO » Sun Feb 06, 2011 10:17 pm

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$.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: BdMO National Higher Secondary 2007/5

Unread post by Masum » Mon Feb 14, 2011 2:06 pm

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
One one thing is neutral in the universe, that is $0$.

Ehsan
Posts:6
Joined:Tue Jan 03, 2012 6:17 pm

Re: BdMO National Higher Secondary 2007/5

Unread post by Ehsan » Tue Feb 07, 2012 4:49 pm

What about the divisibility?

User avatar
sm.joty
Posts:327
Joined:Thu Aug 18, 2011 12:42 am
Location:Dhaka

Re: BdMO National Higher Secondary 2007/5

Unread post by sm.joty » Wed Feb 08, 2012 12:08 am

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.
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

Post Reply