Anyhow bringing 11 in a problem ?

Number Theory Level 4

Given a recurrence relation $a_0=0$ , $a_1=1$ and for $n\geq 2$ , $a_n=6a_{n-1} -9a_{n-2}$ find the remainder when $a_{20}$ is divided by $11$ ?

This is a part of the set 11≡ awesome (mod remainders)

2 9 8 3

1 solution

Chew-Seong Cheong
Sep 16, 2014

We note that $\{a_n\} = \{0, 1, 6, 27, 108, 405, 1458, 5103, 17496, 59049, 196830...\}$

$\Rightarrow a_n = 3^{n-1}n$ for $n > 0$ .

We have $a_{20}=3^{19}(20) = 3^{19}(11 + 9) = 3^{19}(11) + 3^{21}$

Therefore, $a_{20}$ and $3^{21}$ have the same remainder when divided by $11$ .

It is noted that $3^n \equiv a \mod {11}$ , where $a = 1, 3, 9, 5, 4, 1, 3, 9, 5, 4....$ , $a$ repeats in a circle of $5$ . And when $n \equiv 1 \pmod{5}, a = 3$ .

Therefore, the remainder of $a_{20}$ is $\boxed{3}$ .

Is there any shortcut to find the value of those recursive terms? Should I need to calculate every terms to get the set of recursive terms?

Subhajit Ghosh - 6 years, 8 months ago

Subhajit, I used a spreadsheet to do the calculations, which was very easy. And since, I had already got them, I showed a long list. Using hand calculation, you need to find three terms and then induce the rest to be true.

We note that:

$a_1 = 1 = 3^{(1-1)}(1)$

$a_2 = 6 = 3^{(2-1)}(2)$

$a_3 = 27 = 3^{(3-1)}(3)$

$a_4 = 108 = 3^{(4-1)}(4)$

By induction, it implies that $a_n = 3^{(n-1)}n$ for $n > 0$ .

Chew-Seong Cheong - 6 years, 8 months ago

It can also be done without induction. There's a standard way to deal with linear recurrence relations (especially when this one has a characteristic equation with nice roots). Read this .

Note that the characteristic equation of the given recurrence relation is $x^2-6x+9=0$ which has a repeated root of $3$ . Using the method given in that note, the closed form is easily obtained.

Prasun Biswas - 5 years, 10 months ago

Thanks. Yes, I didn't learn it then. I learnt it in Brilliant. I was trained an engineer not mathematician. Anyway, this shows that my solution is original.

Chew-Seong Cheong - 5 years, 10 months ago

Anyhow bringing 11 in a problem ?

1 solution

0 pending reports