an=2n-

å d|n; d < n

ad

Prove that for all n, n|a_n.


Thanks,
Yatir

The sum means

an=2n-

å

ar

where the sum on the right hand side is over all divisors of n (apart from n itself). So for instance:

a₁₂=2¹²-a₁-a₂-a₃-a₄-a₆

Anyway, I think the following works. We have:

å

ar=2n

where the sum is over all positive r which divide into n. The 2ⁿ on the right hand side is the number of subsets of {1,2,¼,n} and so this suggests that we're counting subsets of {1,2,¼,n} in some way.

But how do we incorporate the r|n condition? Well we can write the numbers 1, 2, ..., n on a circle, and we can represent a subset by colouring red all the integers in the subset (and black otherwise). Now it may be that if you rotate the circle a certain amount then the colouring still looks the same - i.e. the sequence of reds and blacks is symmetric under a rotation of angle c units. Note that we would have to have c|n - so this gives us a way of incorporating this condition.

So let's claim that a_m is equal to b_m defined as the number of subsets of {1,2,¼,m} such that if you represent the subset by colouring red numbers on a circle then the sequence of reds and blacks isn't symmetric under any non-trivial rotation.

To do this it suffices to show that:

å

br=2n

where the sum is over all natural r|n because then a_n=b_n follows by induction. I'll leave this to you - write back if you need help.

So anyway we've shown that a_n is the number of subsets on {1,2,¼, n} which aren't symmetric under any rotation when we write them on a circle. Let A be the set of these subsets. We have |a_n|=A so it sufficies to show that n divides into |A|. Well this is quite easy. Define two members of A to be equivalent if you can switch between their representations on the circle by rotation. It is clear that each equivalence class has exactly n elements, and A is a disjoint union of all the equivalence classes, so |A| is a multiple of n, so we're done.

b_n=2ⁿ-aⁿpar

=

å d|n; d ¹ n

ad

a_n=b_n
Though it is hardly a combinatorical proof...

Yatir

Don't understand. a_n is defined as the sequence satisfying your recurrence relationship. Why is a_n+b_n=2ⁿ by definition? b_n is defined as the number of subsets of {1,2,¼,n} such that if you represent this subset by colouring in numbers on a circle, the sequence of colours changes under any non-trivial rotation.

All of this rotation stuff is hard to explain. So let's forget about rotations and circles and stuff, and I'll try and explain more clearly. b_n can be defined as the number of subsets S of {1,2,¼,n} with the property that for any k in {1,2,¼,n-1} there exists u, v in {1,2,¼,n} with v-u=k (mod n) and such that exactly one of u, v is in S.

So we must show that a_n=b_n because then we're done as clearly n|b_n. The way to show that a_n=b_n is to show that b_n satisfies exactly the same recurrence relationship as a_n. (Because it is obvious that the recurrence relationship admits a unique solution, so it follows that a_n=b_n.) So you need to show:

å d|n

bd=2n

where b_n is as defined in my second paragraph. This is, of course, a combinatorial task.

A hint: if S is a subset of {1,2,¼,n} let r(S) be the minimal integer k in {1,2,¼,n} such that for all u, v in {1,2,¼,n} with v-u=k (mod n) we have u in S Leftrightarrow v in S. Note that r(S) always exists because the property is satisfied with k=n (although this will usually not be the minimal allowed integer with this property.

If i is in {1,2,¼,n} define S_i as the set of subsets of S of {1,2,¼,n} such that r(S)=i.

Clearly the set of subsets of {1,2,¼,n} is the disjoint union of S₁, ..., S_n. So:

2ⁿ=|S₁|+|S₂|+¼+|S_n|

Now prove that |S_i|=0 if i doesn't divide into n. If i|n show that |S_i|=b_n/i. Substitute this in, and you have the required recurrence, which completes the proof.