Show that there exist infinitely many $i$ such that $a_i-1$ is divisible by $2^{2015}$

Question

Let $(a_n)$ be a sequence defined by: $a_o=2, a_1=4, a_2=11$ and $\forall n \geq 3$, $$a_n = (n+6)a_{n-1}-3(2n+1)a_{n-2}+9(n-2)a_{n-3}$$

Show that there exist infinitely many $i$ such that $a_i-1$ is divisible by $2^{2015}$

Answer 1

$$a_n = (n+6)a_{n-1}-3(2n+1)a_{n-2}+9(n-2)a_{n-3}$$ can be written as $$a_n-(n+3)a_{n-1}+3(n-1)a_{n-2}=3\left(a_{n-1}-(n+2)a_{n-2}+3(n-2)a_{n-3}\right)$$ So, we can have $$a_n-(n+3)a_{n-1}+3(n-1)a_{n-2}=-3^{n-1}.$$ This can be written as $$a_n-na_{n-1}+n\cdot 3^{n-1}=3\left(a_{n-1}-(n-1)a_{n-2}+(n-1)\cdot 3^{n-2}\right).$$ So, we can have $$a_n-na_{n-1}+n\cdot 3^{n-1}=3^n.$$ This can be written as $$a_n-3^n=n(a_{n-1}-3^{n-1}).$$ So, $$a_n-3^n=n!,$$ i.e. $$a_n=3^n+n!.$$ Now $a_n-1=3^n-1+n!$.

Note here that $3^{2^k}-1$ is divisible by $2^{k+2}$ (you can prove this by induction on $k$). Also, $n!$ is divisible by $i$ at least when $n\ge i$.

Thus, we know that $a_i-1$ is divisible by $2^{2015}$ at least when $i=2^{2015+m}$ where $m=0,1,2,\cdots$.

Hence, it follows from this that there are infinitely many $i$ such that $a_i-1$ is divisible by $2^{2015}$.