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

  • 1
    Since $2^1=\sum_{d\mid 1}a_d$, you must have $a_1=2$.2012-11-02
  • 0
    @Brian: Ah yes :-)2012-11-02
  • 0
    That's what I was going to say. It is a cool solution.2012-11-02
  • 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}$

  • 0
    Is this a combinatorial solution?2012-11-02
  • 0
    @joriki The answer shows that $\dfrac{a_n}n$ counts the number of monic irreducible polynomials of degree $n$ over the field of two elements and hence I believe is a combinatorial solution.2012-11-02
  • 0
    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.2012-11-02
  • 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