Philippines Mathematical Olympiad

Solution:

Let $\{F_{n}\}_{n=1}^{\infty}=\{1,1,2,3,5,8, \ldots\}$ be the sequence of Fibonacci numbers. We first claim that $a_{n}=2^{F_{n}}+1$ for all $n \in \mathbb{N}$. Clearly, this is true for $n=1,2$. Let $k \in \mathbb{N}$ and suppose that the claim is true for $n=k$ and for $n=k+1$. Then
$$\begin{aligned} a_{k+2} & =a_{k+1} a_{k}-a_{k+1}-a_{k}+2 \\ & =\left(a_{k+1}-1\right)\left(a_{k}-1\right)+1 \\ & =2^{F_{k+1}} 2^{F_{k}}+1 \\ & =2^{F_{k+2}}+1 \end{aligned}$$

By strong induction, the claim is proved. Therefore, we now find the remainder when $2^{F_{2020}}+1$ is divided by $22$. To this end, it is easier to find residues modulo $2$ and modulo $11$ and process them to get the residue modulo $22$ (e.g. through Chinese Remainder Theorem).

Clearly, $2^{F_{2020}}$ is even, i.e., $2^{F_{2020}}+1 \equiv 1 \pmod{2}$. We will see later that $2^{F_{2020}}+1 \equiv 0 \pmod{11}$. Therefore, by Chinese Remainder Theorem, $a_{2020}=2^{F_{2020}}+1 \equiv 11 \pmod{22}$.

There are several ways to find the residue of $2^{F_{2020}}+1 \pmod{11}$.

Way 1.1: By Fermat's Little Theorem, $2^{10} \equiv 1 \pmod{11}$. This prompts us to consider the sequence of residues of $F_{n} \pmod{10}$ in order to find $F_{2020} \pmod{10}$:
$$\begin{gathered} \{F_{n} \pmod{10}\}_{n=1}^{\infty}=\{1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1,0, \ldots\} \end{gathered}$$
We see that the sequence is cyclic with period $60$. Therefore, since $2020=60 \times 33 + 40$, we obtain $F_{2020} \equiv 5 \pmod{10}$. Consequently, for some $k \in \mathbb{Z}$,
$$2^{F_{2020}}+1=2^{10k+5}+1 \equiv (2^{10})^{k} 2^{5}+1 \equiv 33 \equiv 0 \pmod{11}$$

Way 1.2: Another way to find $F_{2020} \pmod{10}$ is to get the residues of $F_{2020}$ modulo $2$ and $5$ and process them to find the residue modulo $10$. Again, we list down the sequence of residues modulo $2$ and $5$:
$\{F_{n} \pmod{2}\}_{n=1}^{\infty}=\{1,1,0, \ldots\}$ which has period $3$, and
$$\{F_{n} \pmod{5}\}_{n=1}^{\infty}=\{1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0, \ldots\}$$
which has period $20$. Since $2020 \equiv 1 \pmod{3}$ and $2020 \equiv 0 \pmod{20}$, then $F_{2020} \equiv 1 \pmod{2}$ and $F_{2020} \equiv 0 \pmod{5}$. Therefore, $F_{2020} \equiv 5 \pmod{10}$ by Chinese Remainder Theorem. Thus, the result holds.

Solution 2:

Inspired by the factorization in (1), we define $b_{n}=a_{n}-1$ for all $n \in \mathbb{N}$. Then $b_{1}=b_{2}=2$ and (1) simplifies to
$$b_{n+2}=b_{n+1} b_{n}$$
We observe that $b_{1}=2^{F_{1}}$, $b_{2}=2^{F_{2}}$, and (3) implies $b_{3}=2^{F_{3}}$. This pattern continues and obviously shows that $b_{n}=2^{F_{n}}$ for all $n \in \mathbb{N}$. Very similar arguments to Solution 1 will give $b_{2020} \equiv 0 \pmod{2}$ and $b_{2020} \equiv 10 \pmod{11}$. Therefore, by Chinese Remainder Theorem, $b_{2020} \equiv 10 \pmod{22}$. Equivalently, $a_{2020} \equiv 11 \pmod{22}$.

Solution 3:

By bashing, we can list down the residues of $\{a_{n}\}_{n=1}^{\infty}$ (or of $\{b_{n}\}_{n=1}^{\infty}$ as defined in Solution 2):
$$\begin{aligned} &\{a_{n} \pmod{22}\}_{n=1}^{\infty}=\{3,3,5,9,11,15,9,3,17,11,7,17,9,19,13,19,19,17,3,11,21,3,19,15, \\ & 11,9,15,3,7,13,7,7,15,19,11,5,19,7,21,11,3,21,19,9,13,9,9,21,7,11, \\ & 17,7,9,5,11,19,5,7,3,13, \ldots\} \end{aligned}$$
Since the sequence is cyclic with period $60$, and $2020 \equiv 40 \pmod{60}$, then $a_{2020} \equiv 11 \pmod{22}$.