MHB What is the remainder when a_{2013} is divided by 7?

[anemone]

Consider a sequence given by $$a_n=a_{n-1}+3a_{n-2}+a_{n-3}$$, where $$a_0=a_1=a_2=1$$.

What is the remainder of $$a_{2013}$$ divided by $$7$$?

 

[chisigma]

Consider a sequence given by $$a_n=a_{n-1}+3a_{n-2}+a_{n-3}$$, where $$a_0=a_1=a_2=1$$.

What is the remainder of $$a_{2013}$$ divided by $$7$$?

Operating modulo 7 we have...

$$a_{0}=1$$
$$a_{1}=1$$
$$a_{2}= 1$$
$$a_{3} = 1 + 3 + 1 = 5$$
$$a_{4} = 5 + 3 + 1 = 2\ \text{mod}\ 7$$
$$a_{5} = 2 + 1 + 1 = 4\ \text{mod}\ 7$$
$$a_{6} = 4 + 6 + 5 = 1\ \text{mod}\ 7$$
$$a_{7} = 1 + 12 + 2 = 1\ \text{mod}\ 7$$
$$a_{8} = 1 + 3 + 4 = 1\ \text{mod}\ 7$$
$$a_{9} = 1 + 2 + 1 =5\ \text{mod}\ 7$$

... and we can stop because the sequence is mod 7 periodic with period 6. Now is $2013\ \text{mod}\ 6 = 3$, so that the requested number is $a_{3}=5$...

Kind regards

$\chi$ $\sigma$

 

[Opalg]

I agree with chisigma on the level of algebra, but not on the level of arithmetic. In fact, reducing all the coefficients mod 7 as we go along,

$a_{n+3} = a_{n+2} + 3a_{n+1} + a_{n}$,

$a_{n+4} = a_{n+3} + 3a_{n+2} + a_{n+1} = (a_{n+2} + 3a_{n+1} + a_{n}) + 3a_{n+2} + a_{n+1} = 4a_{n+2} + 4a_{n+1} + a_{n}$,

$a_{n+5} = a_{n+4} + 3a_{n+3} + a_{n+2} = (4a_{n+2} + 4a_{n+1} + a_{n}) + 3(a_{n+2} + 3a_{n+1} + a_{n}) + a_{n+2} = a_{n+2} + 6a_{n+1} + 4a_{n}$,

$a_{n+6} = a_{n+5} + 3a_{n+4} + a_{n+3} = (a_{n+2} + 6a_{n+1} + 4a_{n}) + 3(4a_{n+2} + 4a_{n+1} + a_{n}) + (a_{n+2} + 3a_{n+1} + a_{n}) = a_{n}$

(for all $n\geqslant0$). So the sequence repeats with period $6$. It starts with $(a_0,a_1,a_2,a_3,a_4,a_5) = (1,1,1,5,2,4)\pmod7$, and since $2013=3\pmod6$ it follows that $a_{2013} = a_3 = 5\pmod7.$

 

[anemone]

Thanks to both chisigma and Opalg for the submission to this problem and I've been really impressed with the creativity that gone into the two approaches above and please allow me to thank you all again for the time that the two of you have invested to participate in this problem. :)