Combinatoria solución a una recurrencia del problema

Question

Me he encontrado hoy este problema en algunos viejos post en el blog:

Supongamos que $a_n$ es una secuencia de enteros positivos tales que $$ \sum_{d |n} a_d =2^n$$ for every positive integer $n$. Prove that $ n | a_n$.

Parece como una especie de inducción podría trabajar (trabajo con el primer divisores, etc...), pero yo estoy interesado en una diferente, y posiblemente la solución más elegante:

En mis notas me han escrito que este tiene una combinatoria solución, pero me parece que no puede averiguar ahora. Puede usted ayudarme por favor?

Answer 1

Ya que la mayor plazo en la suma es linealmente determinado por todas las inferiores, y $a_1=2$ (como Brian señalado), esta es una recurrencia de la relación única que determina todos los $a_n$. Por lo tanto, es suficiente para exponer una secuencia que satisface la relación de recurrencia.

El lado derecho cuenta el número de secuencias binarias de longitud $n$. El lado izquierdo cuenta estas secuencias de acuerdo a su (primitivo cíclico) períodos de $d$, que se debe dividir $n$. El número de secuencias con período de $d$ es divisible por $d$, ya que cada secuencia está en una clase de equivalencia de a $d$ secuencias relacionadas por turnos.

Tenga en cuenta que esto funciona debido a que el número de $a_d$ de las secuencias con período de $d$ es independiente de su longitud $n$ y sólo depende de $d$.