# Divisibility of term in exponential recurrence relation

I found the problem here: http://www.artofproblemsolving.com/community/c7h1314296_2x15_is_divisible_by_x

$\large a_1 = 3$

$\large a_{n+1} = 2^{a_n -1} +5$

Prove:

$\large a_n|a_{n+1}$

Initially I tried inducting but found no way to make the statement carry on to the next recurrence.

This problem seems fairly interesting and I wonder if it can be done using elementary means.

The first four values of $a_n$ are as follows:

$3, 9, 261,$

$1852673427797059126777135760139006525652319754650249024631321344126610074238981$

Mathematica verifies the divisibility of $a_4$ by $a_3$, so the statement does appear to hold water.

• Mathematica also verifies (using PowerMod) that $a_4\mid a_5$. – Greg Martin Oct 6 '16 at 6:22
• Fiddling around with this function. $a_n$ is always odd because its is $2^n + 5$. It will also be divisible by 3 because $2^n mod 3$ is 1 when n is even. – Q the Platypus Oct 7 '16 at 1:01
• See mathoverflow.net/questions/251717/… for extensive discussion. – Max Alekseyev Oct 9 '16 at 13:05