The sequence $a_1$, $a_2$, $a_3,$ $\dots$ is defined by $a_1 = 1,$ $a_2 = 3,$ and

a_n = 2a_{n - 1} + a_{n - 2}.

Thus, the next few terms are $a_3 = 2a_2 + a_2 = 6 + 1 = 7$ and $a_4 = 2a_3 + a_2 = 14 + 3 = 17$.



Find the remainder when $a_8$ is divided by $3.$

1 answer

To determine the remainder of \(a_8\) when divided by \(3\), we first identify a pattern in the sequence modulo \(3\). We begin with the sequence definition:

\[
a_n = 2a_{n-1} + a_{n-2}
\]

Given initial terms:
\[
a_1 = 1 \quad \text{and} \quad a_2 = 3
\]

Calculating the terms modulo \(3\):

\[
a_1 \equiv 1 \pmod{3}
\]

\[
a_2 \equiv 0 \pmod{3}
\]

Next, we find \(a_3\):

\[
a_3 = 2a_2 + a_1 = 2 \cdot 3 + 1 = 6 + 1 = 7 \quad \implies \quad a_3 \equiv 1 \pmod{3}
\]

Then, we calculate \(a_4\):

\[
a_4 = 2a_3 + a_2 = 2 \cdot 7 + 3 = 14 + 3 = 17 \quad \implies \quad a_4 \equiv 2 \pmod{3}
\]

We continue the calculations for the next terms:

\[
a_5 = 2a_4 + a_3 = 2 \cdot 17 + 7 = 34 + 7 = 41 \quad \implies \quad a_5 \equiv 2 \cdot 2 + 1 = 4 + 1 = 5 \equiv 2 \pmod{3}
\]

\[
a_6 = 2a_5 + a_4 = 2 \cdot 41 + 17 = 82 + 17 = 99 \quad \implies \quad a_6 \equiv 2 \cdot 2 + 2 = 4 + 2 = 6 \equiv 0 \pmod{3}
\]

\[
a_7 = 2a_6 + a_5 = 2 \cdot 99 + 41 = 198 + 41 = 239 \quad \implies \quad a_7 \equiv 2 \cdot 0 + 2 = 0 + 2 = 2 \pmod{3}
\]

Finally, \(a_8\):

\[
a_8 = 2a_7 + a_6 = 2 \cdot 239 + 99 = 478 + 99 = 577 \quad \implies \quad a_8 \equiv 2 \cdot 2 + 0 = 4 + 0 = 4 \equiv 1 \pmod{3}
\]

Thus, the remainder when \(a_8\) is divided by \(3\) is

\[
\boxed{1}
\]