# Combinatorial solution to a recurrence problem

I found today this problem in some old blog post:

Suppose that $a_n$ is a sequence of positive integers such that $$\sum_{d |n} a_d =2^n$$ for every positive integer $n$. Prove that $n | a_n$.

It seems like a sort of induction could work (working with prime divisors, etc...), but I am interested in a different, and possibly more elegant solution:

In my notes I have written that this has a combinatorial solution, but I can't seem to figure it out now. Can you please help me?

-

Since the highest term in the sum is linearly determined by all the lower ones, and $a_1=2$ (as Brian pointed out), this is a recurrence relation that uniquely determines all $a_n$. Thus it suffices to exhibit a sequence that fulfills the recurrence relation.

The right-hand side counts the number of binary sequences of length $n$. The left-hand side counts these sequences according to their (primitive cyclical) periods $d$, which must divide $n$. The number of sequences with period $d$ is divisible by $d$, since each sequence is in an equivalence class of $d$ sequences related by shifts.

Note that this works because the number $a_d$ of sequences with period $d$ is independent of their length $n$ and depends only on $d$.

-
Since $2^1=\sum_{d\mid 1}a_d$, you must have $a_1=2$. –  Brian M. Scott Nov 2 '12 at 22:12
@Brian: Ah yes :-) –  joriki Nov 2 '12 at 22:13
That's what I was going to say. It is a cool solution. –  Beni Bogosel Nov 2 '12 at 22:13
@Beni: See OEIS A027375 and OEIS A001037. –  Brian M. Scott Nov 2 '12 at 22:15

By Möbius inversion formula, we have that $$a_n = \sum_{d \vert n} \mu(d) 2^{n/d} = n M_n(2)$$ where $M_n(2)$ is the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_2$.

And look here why $\displaystyle n \vert \sum_{d \vert n} \mu(d) 2^{n/d}$

-
Is this a combinatorial solution? –  joriki Nov 2 '12 at 22:02
@joriki The answer shows that $\dfrac{a_n}n$ counts the number of monic irreducible polynomials of degree $n$ over the ﬁeld of two elements and hence I believe is a combinatorial solution. –  user17762 Nov 2 '12 at 22:07
A combinatorial solution isn't a solution that shows that something counts some number, but one that shows something by counting. What you mean is sort of the dual of a combinatorial solution, an analytic solution to a combinatorial problem. –  joriki Nov 2 '12 at 22:09
Usually Mobius inversion is tied to combinatorics. It is not what I had in mind, but is is still a nice solution. Thanks –  Beni Bogosel Nov 2 '12 at 22:15