Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
1  
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}$

share|improve this answer
    
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 field 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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.