Home > Combinatorics, IMO, Olympiad, Problem Solving > Interesting recurrence

## Interesting recurrence

Suppose that $(a_n)_{n\geq 1}$ is a sequence of integers such that $\displaystyle \sum_{d | n}a_d=2^n$ for all positive integers $n$. Prove that $n | a_n$ for all $n \geq 1$.

Hint Try a combinatorial approach. Note that $a_n$ is uniquely defined, and $a_n$ can be taken as the number of  binary sequences of length $d$.

For more details see this question on Math SE

Or you can try it by induction. First note that $a_1=2$ and for $p$ prime we have $a_n=2^p-2$. Then work with more factors inductively.