Estonian Mathematical Olympiad

$$c_n=(c_1\cdots c_{n-2})\cdot c_{n-1}=c_{n-1}^2.$$ Since $a_4=5^2=25$ and $c_4=2\cdot 3\cdot 5=30$, we have $a_n<c_n$ for any $n\ge 4$. Next note that $c_1=b_1=2$, $c_2=b_2=3$, $c_3=b_3=5$ and $$c_4=30<60=b_4,c_5=900<2700=b_5,c_6=810000<4050000=b_6.$$ Now prove by induction that $c_n<b_n$ for any $n\ge 7$. Assume that the statement holds for every $m$ with $4\le m<n$. As $c_{n-3}=c_{n-4}\cdot c_{n-5}\cdot \cdots \cdot c_1$, we get $c_n=c_{n-1}{c}_{n-2}{c}_{n-3}{c}_{n-4}\dots c_1=c_{n-1}{c}_{n-2}{c}_{n-3}^2<b_{n-1}{b}_{n-2}{b}_{n-3}^2=b_n$, which we wanted to prove. Hence $a_n<c_n<b_n$ for any $n\ge 4$.

---

Alternative solution.

As in Solution 1 show that $a_n<c_n$ for any $n\ge 4$. To show that $c_n<b_n$ for any $n\ge 4$ we prove by induction that $b_n\ge c_n{c}_{n-3}$; since $c_{n-3}>1$ for $n\ge 4$, it follows $b_n>c_n$ for any $n\ge 4$. For simplicity define $c_0=c_{-1}=c_{-2}=1$; then the inequality $b_n\ge c_n{c}_{n-3}$ holds for $n=1,2,3$ as equality and for $n\ge 4$ we have $c_n=c_{n-1}{c}_{n-2}\dots c_{-2}$. So assuming the hypothesis holds for $n-1,n-2$ and $n-3$, we get for $n\ge 4$ $$\begin{array}{rl}{b}_n& =b_{n-1}{b}_{n-2}{b}_{n-3}^2\ge c_{n-1}{c}_{n-4}{c}_{n-2}{c}_{n-5}{c}_{n-3}{c}_{n-6}{c}_{n-3}{c}_{n-6}\\ & =(c_{n-1}\dots c_{n-6})c_{n-3}{c}_{n-6}.\end{array}$$ If $n\le 8$ or $n\ge 10$ then $c_{n-6}\ge c_{n-7}\dots c_{-2}$, hence $$c_{n-1}\dots c_{n-6}\cdot c_{n-6}\ge c_{n-1}\dots c_{-2}=c_n.$$ So in these cases $b_n\ge c_n\cdot c_{n-3}$. It remains to observe that $$\begin{array}{rl}{b}_9& =b_8{b}_7{b}_6^2=b_7{b}_6{b}_5^2\cdot b_7{b}_6^2=b_7^2{b}_6^2{b}_5^2\cdot b_6\\ & \ge (c_7{c}_4{)}^2(c_6{c}_3{)}^2(c_5{c}_2{)}^2\cdot c_6{c}_3=(c_7{c}_6{c}_5{c}_4{c}_3{c}_2{)}^2\cdot c_6\cdot 5\\ & >(c_7{c}_6{c}_5{c}_4{c}_3{c}_2{)}^2\cdot c_6\cdot 4=(c_7{c}_6{c}_5{c}_4{c}_3{c}_2{c}_1{)}^2\cdot c_6=c_8^2\cdot c_6=c_9\cdot c_6.\end{array}$$ Consequently the inequality holds in all cases.

---

Alternative solution.

By mathematical induction it is easy to see that $a_n=5^{2^{n-3}}$ for any $n\ge 3$. Indeed it is true for $n=3$ and if $n>3$ and the claim holds for $n-1$ then $a_n=a_{n-1}^2=(5^{2^{n-4}}{)}^2=5^{2^{n-4}\cdot 2}=5^{2^{n-3}}$ so it holds for $n$. Also $c_n=2^{2^{n-4}}{3}^{2^{n-4}}{5}^{2^{n-4}}$ for any $n\ge 4$. Indeed it is true for $n=4$ because $c_4=2\cdot 3\cdot 5=2^1{3}^1{5}^1=2^{2^0}{3}^{2^0}{5}^{2^0}$, and if $n>4$ and the claim holds for $n-1$ then $$\begin{array}{rl}{c}_n& =c_{n-1}\cdot c_{n-2}\dots c_1=c_{n-1}^2\\ & =(2^{2^{n-5}}{3}^{2^{n-5}}{5}^{2^{n-5}}{)}^2=(2^{2^{n-5}}{)}^2(3^{2^{n-5}}{)}^2(5^{2^{n-5}}{)}^2\\ & =2^{2^{n-5}\cdot 2}{3}^{2^{n-5}\cdot 2}{5}^{2^{n-5}\cdot 2}=2^{2^{n-4}}{3}^{2^{n-4}}{5}^{2^{n-4}}\end{array}$$ so the claim holds for $n$. Hence for any $n\ge 4$ we have $$c_n=6^{2^{n-4}}{5}^{2^{n-4}}>5^{2^{n-4}}{5}^{2^{n-4}}=5^{2^{n-4}+2^{n-4}}=5^{2^{n-3}}=a_n.$$ Consider the sequence $b_n$. Clearly $b_n$ is a product of powers of primes 2, 3 and 5. From the definition of $(b_n)$ for all $n\ge 4$ the powers of $p=2,3,5$ satisfy $v_p(b_n)=v_p(b_{n-1})+v_p(b_{n-2})+2v_p(b_{n-3})$. Calculate the powers of 2, 3 and 5 in the canonical representation of the first 9 terms:

n	1	2	3	4	5	6	7	8	9
$v_2(b_n)$	1	0	0	2	2	4	10	18	36
$v_3(b_n)$	0	1	0	1	3	4	9	19	36
$v_5(b_n)$	0	0	1	1	2	5	9	18	37

We see that $v_p(b_n)>2^{n-4}$ for $n=7,8,9$ and $p=2,3,5$. But if $v_p(b_{n-1})>2^{n-5}$, $v_p(b_{n-2})>2^{n-6}$ and $v_p(b_{n-3})>2^{n-7}$ for some $n\ge 4$, then $$\begin{array}{rl}{v}_p(b_n)& =v_p(b_{n-1})+v_p(b_{n-2})+2v_p(b_{n-3})\\ & >2^{n-5}+2^{n-6}+2\cdot 2^{n-7}\\ & =2^{n-5}+2^{n-6}+2^{n-6}=2^{n-5}+2^{n-5}=2^{n-4}.\end{array}$$ So by mathematical induction $v_p(b_n)>2^{n-4}$ for all $n\ge 7$ and $p=2,3,5$. Consequently $c_n<b_n$ for all $n\ge 7$.