BdMO 2017 National Round Secondary 8

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
Kazi_Zareer
Posts: 86
Joined: Thu Aug 20, 2015 7:11 pm
Location: Malibagh,Dhaka-1217

BdMO 2017 National Round Secondary 8

The sequence $\left \{ a_n \right \}$ is defined by $a_{n+1} = 2(a_n - a_{n-1}),$ where $a_0 = 1,$ $a_1 = 1$ for all positive integers $n.$ What is the remainder of $a_{2016}$ upon division by $2017$? Provide a proof of your answer.
We cannot solve our problems with the same thinking we used when we create them.

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

Re: BdMO 2017 National Round Secondary 8

The sequence is actually $\dfrac{(1+i)^n+(1-i)^n}{2}$. It is easy to prove it by induction.

Now, $(1+i)^8=(1-i)^8=2^4$ and $2016=8\times 252$, so $a_{2016}=2^{1008}$.

Now, note that $\displaystyle \prod_{k=1}^{1008}2k=2^{1008}\times 1008!$

Again, $\displaystyle \prod_{k=1}^{1008}2i=\prod_{k=1}^{504}2k\times \prod_{k=505}^{1008}2k$. Calculating in mod $2017$, we get $\displaystyle \prod_{k=505}^{1008}2k\equiv \prod_{k=505}^{1008}(2k-2017)\equiv \prod_{k=1}^{504}(2k-1)$.

So, $\displaystyle \prod_{k=1}^{1008}2k\equiv 1008!$.

Therefore, $2^{1008}1008!\equiv 1008!$. So, $2^{1008}\equiv 1$. So, the remainder is $1$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Tasnood
Posts: 73
Joined: Tue Jan 06, 2015 1:46 pm

Re: BdMO 2017 National Round Secondary 8

I think the first step has come through it:
We can right:$a_{n+1}=2a_n-2a_{n-1} \Rightarrow a_n=2a_{n-1}-2a_{n-2} \Rightarrow r^2=2r-2 \Rightarrow r^2-2r+2=0$
$r=\frac{-(-2)+\sqrt{(-2)^2-4.1.2}}{2.1}$ or,$\frac{-(-2)-\sqrt{(-2)^2-4.1.2}}{2.1}$
$\Rightarrow r=(1+i) or, (1-i)$ [Because $\sqrt{(-2)^2-4.1.2}=\sqrt{4-8}=\sqrt{-4}$ which denotes imaginary unit]

So, we get:$\alpha =1+i$,$\beta =1-i$
So, $a_n=A \alpha ^n+B \beta ^n$

We know:$A+B=a_0=1$,$A \alpha +B \beta =a_1 \Rightarrow A(1+i)+B(1-i)=1 \Rightarrow (A+B)+i(A-B)=1 \Rightarrow A-B=0 \Rightarrow A=B$
So, $A=B=\frac{1}{2}$

So, $a_n=A \alpha ^n+B \beta ^n$
$\Rightarrow a_n=\frac{1}{2}(1+i)^n+\frac{1}{2}(1-i)^n$
$\Rightarrow a_n=\frac{(1+i)^n+(1−i)^n}{2}$

Then, just need to use the De Moivre's formula: For any complex number $x$ and integer $n$ it holds that that $(cos (x)+i \times sin (x))^n=cos (nx)+i \times sin (nx)$ ;where $i$ is imaginary unit [$i^2=-1$]
I think I am in right way