If $a_n = 2^{n-1}(2^{n-1}-1)a_{n-1}$, $a_1=1$, show that $n \mid a_n$

Question

If$$a_n = 2^{n-1}(2^{n-1}-1)a_{n-1},\ a_1=1,\ a_2= 2,\ a_3=24,$$ Show that $n \mid a_n $.

I've obtained $a_n =2^{\frac{n(n-1)}{2}}M_{n-1}$, where $M_n$ is the $n$^th Mersenne number. What would be the best way to proceed from here?

Answer 1

Define $c_n = [1, 2, \cdots, n]$ for all $n \in \mathbb{N}_+$, i.e. $c_n$ is the least common multiple of $1, 2, \cdots, n$. It will be proved by induction on $n$ that $c_n \mid a_n$. The base case is trivial.

Now suppose $c_{n - 1} \mid a_{n - 1}$. Note that$$ c_n = \begin{cases} p c_{n - 1}; & n = p^m \text{ for some prime } p\\ c_{n - 1}; & \text{otherwise} \end{cases}. $$

Case 1: $n = p^m$ for some odd prime $p$. By Fermat's little theorem, there is$$ 2^n = 2^{p^m} = (2^p)^{p^{m - 1}} \equiv 2^{p^{m - 1}} \equiv \cdots \equiv 2 \pmod{p}, $$ thus$$ p \mid 2^{n - 1} - 1 \Longrightarrow \frac{a_n}{c_n} = 2^{n - 1}·\frac{2^{n - 1} - 1}{p}·\frac{a_{n - 1}}{c_{n - 1}} \in \mathbb{Z} \Longrightarrow c_n \mid a_n. $$

Case 2: $n = 2^m$. Because $n = 2^m \geqslant 2$, then$$ \frac{a_n}{c_n} = (2^{n - 1} - 1)·2^{n - 2}·\frac{a_{n - 1}}{c_{n - 1}} \in \mathbb{Z} \Longrightarrow c_n \mid a_n. $$

Case 3: Otherwise $c_n = c_{n - 1}$, then$$ \frac{a_n}{c_n} = (2^{n - 1} - 1)·2^{n - 1}·\frac{a_{n - 1}}{c_{n - 1}} \in \mathbb{Z} \Longrightarrow c_n \mid a_n. $$

Therefore $c_n \mid a_n$ always holds. End of induction.

Now, since $n \mid c_n$ and $c_n \mid a_n$, then $n \mid a_n$ for all $n$.

Answer 2

Let $n$ and put $n=2^jm$ where $m$ is odd. Because $2^j\leq n\leq 2^{n-1}$ for all $n$, the factor $2^{n-1}$ have all even part of $n$.

Now, we can prove that $a_n$ is multiple of $m$. This is because $a_n$ is multiple of $a_m$ and, by induction, $a_m$ is multiple of $m$ (remember that $m<n$).