4
$\begingroup$

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?

2 Answers 2

4

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$.

  • 0
    @Beni: See [OEIS A027375](http://oeis.org/A027375) and [OEIS A001037](http://oeis.org/A001037).2012-11-02
2

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}$

  • 1
    Usually Mobius inversion is tied to combinatorics. It is not what I had in mind, but is is still a nice solution. Thanks2012-11-02