A recurrence relation

Probability Level 4

Let $a_0,a_1,\cdots$ be a sequence defined by $a_0=7$ , $a_1=8$ , and, for all $n\ge 2$ , $a_n=5a_{n-1}-6a_{n-2}$ Find the remainder when $a_{2014}$ is divided by 1000.

See here for information regarding recurrence relations.

The answer is 178.

1 solution

Daniel Chiu
Jan 19, 2014

The characteristic polynomial is $x^2-5x+6=(x-2)(x-3)$ so the closed-form looks like $a_n=c_1(2^n)+c_2(3^n)$ Using the initial values, $c_1+c_2=7$ $2c_1+3c_2=8$ Solving, $c_1=13$ and $c_2=-6$ . Thus, $a_n=13(2^n)-6(3^n)$ With $n=2014$ and modulo 1000, $\begin{aligned} 13(2^{2014})-6(3^{2014})&\equiv 13(2^{14})-6(3^{14})\pmod{1000} \\ &\equiv 13(384)-6(969)\pmod{1000} \\ &\equiv \boxed{178}\pmod{1000} \end{aligned}$ where the first step follows from Euler's totient theorem ( $a^{400}\equiv 1\pmod{1000}$ ) and the second step follows from expanding out the powers.

If I remember correctly, Euler's Theorem states that, $\large a^{\phi(n)}\equiv 1 \pmod{n}, \quad \textrm{if}~\gcd(a,n)=1 \land a,n\in \mathbb{Z^+}$

So, using Euler's theorem with $a=3,n=1000$ works since $\gcd(3,1000)=1$ , but how can we use it for $a=2,n=1000$ when $\gcd(2,1000)=2\neq 1~?$

Correct me if I'm wrong. Thanks in advance. :)

Prasun Biswas - 6 years, 5 months ago

Your critique is correct.

He was lucky that the calculations work out. This happens because $14 > 3$ and $2^3 \mid \mid 1000$ . As you were hinting, the right way to do this is $2^{2014} \equiv 0 \pmod{8}$ and $2^{2014} \equiv 2^{14} \pmod{125}$ . Combining that gives us $2^{2014} \equiv 2^{14} \pmod{125}$ by CRT. Note that $2^{2001} \not \equiv 2^1 \pmod{1000}$ .

Calvin Lin Staff - 3 years, 9 months ago

A recurrence relation

The answer is 178.

1 solution

0 pending reports