Balkan Mathematical Olympiad Shortlist

Consider the sequence $b_0,b_1,\dots$, defined by the initial conditions $b_0=1$, $b_1=2$, and the recursion $b_{n+1}=4b_n-b_{n-1}$ for $n\ge 1$. We have $a_n=b_{n+1}-1$, for all $n\ge 0$. In particular, $a_{2^k-1}=b_{2^k}-1$, $k\ge 0$. It is not hard to see that the general formula for $b_n$ is $$b_n=\frac{(2+\sqrt{3}{)}^n+(2-\sqrt{3}{)}^n}{2},n\ge 2.(1)$$ Let $k\ge 3$ be fixed. It follows from (1) that $b_{2^k}={\sum }_{j=0}^{2^{k-1}}\left(\genfrac{}{}{0ex}{}{2^k}{2j}\right)2^{2^k-2j}{3}^j$ and thus $$b_{2^k}\equiv 1(\mathrm{mod}3)\text{ and }{b}_{2^k}\equiv 1(\mathrm{mod}4).(2)$$ It is easy to see that the terms of the sequence, defined by $c_n=\frac{(2+\sqrt{3}{)}^n-(2-\sqrt{3}{)}^n}{2\sqrt{3}}$, are positive integers, which satisfy $b_n^2-3c_n^2=1$ for all $n\in \mathbb{N}$. In particular, we have $$b_{2k}^2-1=3c_{2k}^2.\text{\hspace{1em}(3)}$$ Applying the identity $(x^{2^s}-y^{2^s})(x^{2^s}+y^{2^s})=(x^{2^{s+1}}-y^{2^{s+1}})$ with $x=2+\sqrt{3}$ and $y=2-\sqrt{3}$ for $s=0,1,\dots ,k-1$, we get $$2\sqrt{3}\prod _{j=0}^{k-1}(2b_{2^j})=(2+\sqrt{3}{)}^{2k}-(2-\sqrt{3}{)}^{2k}.$$ Therefore, $$c_{2^k}=2^{k+1}{b}_2{b}_{2^2}\dots b_{2^{k-1}}.(4)$$ It follows from (2) and (3) that $$2\mid b_{2^k}+1;\text{ and }\gcd (b_{2^j},6)=1\text{ for every }j=1,2,\dots ,k-1.(5)$$ Since $b_{2^k}+1\equiv 2(\mathrm{mod}3)$, by (3), (4) and (5) we have $$3\mid b_{2^k}-1\text{ and }{2}^{2^{k+1}}\mid b_{2^k}-1.(6)$$ Now, suppose that there exists an $m\ge 3$ such that $b_{2^m}-1$ has at most two prime factors. Then it follows from the relations in (2) that these prime factors must be 2 and (or) 3. Furthermore, (6) implies that we must have $b_{2^m}=2^{2^{m+1}}\cdot 3+1$ (7). Therefore, by (3) we get $$c_{2^m}^2=\frac{b_{2^m}^2-1}{3}=4^{m+1}(3.4^m+1).(8)$$ On the other hand, by (4) we have $c_{2^m}^2=4^{m+1}{\prod }_{j=1}^{m-1}{b}_{2^j}^2>4^{m+1}(3c_{2^{m-1}}+1)$, and thus $c_{2^m}^2>4^{m+1}(3.4^m+1)$ as $c_{2^{m-1}}\ge 2^m$ by (4). This is a contradiction to (8) and therefore $a_{2^{k-1}}$ has at least three prime factors for every positive integer $k\ge 3$.

Alternative solution:

This approach is based on the fact that all linear sequences are periodic modulo arbitrary positive integer. We show that $a_{2^{k-1}}$ is divisible by $2$, $3$, $7$. Observe that if $a_n$ is even for some $n$, then $a_{n+2}=4a_{n+1}-a_n+2$ is also even. Since $a_1=6$ is even, we conclude that $a_{2t-1}$ is even for all positive integers $t$. Therefore, $a_{2^{k-1}}$ is even. Let $b_n=a_n(\mathrm{mod}3)$. Since $b_0=1$ and $b_1=0$, it follows by induction that $b_{2t}=1$ and $b_{2t+1}=0$. Hence, $b_{2^{k-1}}=0$, i.e. $a_{2^{k-1}}$ is divisible by $3$. Let $c_n=a_n(\mathrm{mod}7)$. We have $$c_0=1,c_1=-1,c_2=-3,c_3=-2,c_4=-3,c_5=-1,c_6=1,c_7=0,c_8=1,c_9=-1.$$ Since $c_0=1$, $c_1=-1$ and $c_8=1$, $c_9=-1$, we conclude that the sequence $c_1,c_2,\dots$ is periodic with period $8$. It follows from $c_7=0$ that $c_{7+8t}=0$ for all positive integers $t$. It remains to notice that $2^k-1=7+8(2^{k-3}-1)$, implying that $c_{2^{k-1}}=0$. Therefore, $a_{2^{k-1}}$ is divisible by $7$.