$a_n=2^n-\sum _{d|n;d<n}{a}_d$

Prove that for all $n$, $n|a_n$.


Thanks,
Yatir

The sum means $a_n=2^n-\sum a_r$ where the sum on the right hand side is over all divisors of $n$ (apart from $n$ itself). So for instance:

$a_{12}=2^{12}-a_1-a_2-a_3-a_4-a_6$

Anyway, I think the following works. We have:

$\sum a_r=2^n$

where the sum is over all positive $r$ which divide into $n$. The $2^n$ on the right hand side is the number of subsets of $\{1,2,\dots ,n\}$ and so this suggests that we're counting subsets of $\{1,2,\dots ,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,\dots ,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:

$\sum b_r=2^n$

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,\dots ,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 $\left|a_n\right|=A$ so it sufficies to show that $n$ divides into $\left|A\right|$. 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 $\left|A\right|$ is a multiple of $n$, so we're done.

$b_n=2^n-a^n$par $=\sum _{d|n;d\ne n}{a}_d$

$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^n$ by definition? $b_n$ is defined as the number of subsets of $\{1,2,\dots ,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,\dots ,n\}$ with the property that for any $k$ in $\{1,2,\dots ,n-1\}$ there exists $u$, $v$ in $\{1,2,\dots ,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:

$\sum _{d|n}{b}_d=2^n$

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,\dots ,n\}$ let $r(S)$ be the minimal integer $k$ in $\{1,2,\dots ,n\}$ such that for all $u$, $v$ in $\{1,2,\dots ,n\}$ with $v-u=k$ (mod $n$) we have $u$ in $S$ $\mathrm{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,\dots ,n\}$ define $S_i$ as the set of subsets of $S$ of $\{1,2,\dots ,n\}$ such that $r(S)=i$.

Clearly the set of subsets of $\{1,2,\dots ,n\}$ is the disjoint union of $S_1$, ..., $S_n$. So:

$2^n=\left|S_1\right|+\left|S_2\right|+\dots +\left|S_n\right|$

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