$\boxed{A6}$The sequence $a_0,a_1,...$ is defined by the initial conditions $a_0=1,a_1=6$ and the recursion $a_{n+1}=4a_n-a_{n-1}+2$ for $n>1.$Prove that $a_{2^k-1}$ has at least three prime factors for every positive integer $k>3.$
Problem
Source: Balkan MO 2014 Shortlist
Tags: Sequence, algebra
01.10.2016 13:56
Ignore this I through $a_1=1$ and $a_2=6$
01.10.2016 14:31
Taking $\pmod 3$ we observe that $a_{2m+1}$ is always divisible by $3$, so there is some mistake in your computation I think.
01.10.2016 15:32
Easy to see that $a_{2m-1}=6b_m^2$ for all $m\in \mathbb{Z}^+$ where $\{ b_n\}_{n\in \mathbb{Z}^+}$ is defined by $b_0=0,b_1=1$ and $b_n=4b_{n-1}-b_{n-2}$ for all $n\in \mathbb{Z}^+$ So $a_{2^k-1}=6b_{2^{k-1}}^2$ for all $k>3$, so we need to show that $b_{2^k}$ contain prime divisor $\neq 2,3$ for all $k\geq 3$ We have $b_n=\frac{(2+\sqrt{3})^n-(2-\sqrt{3})^n}{2\sqrt{3}}$ for all $n\in \mathbb{Z}^+$ So $v_2(b_{2^k})=\left( v_2(4)+v_2(2\sqrt{3})+v_2(2^k)-1\right) -v_2(2\sqrt{3})=k+1$ for all $k\geq 1$ And we have $b_{2^k} =((2+\sqrt{3})+(2-\sqrt{3}))((2+\sqrt{3})^2+(2-\sqrt{3})^2)((2+\sqrt{3})^4+(2-\sqrt{3})^4)\times ...\times ((2+\sqrt{3})^{2^{k-1}}+(2-\sqrt{3})^{2^{k-1}})$ So $3\nmid b_{2^k}$ for all $k\geq 1$ Since $v_2(b_{2^k})=k+1,v_3(b_{2^k})=0$, it is enough to show that $b_{2^k} >2^{k+1}$ for all $k\geq 3$ which is easy.