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.

Let $A(n)$ - is the set of natural numbers $\{1,2, \dots ,n\}$.

Let $B$ - is any subset of $A(n)$. And $S(B)$ is the sum of all elements $B$.

Subset $B$ is "special subset" if $S(B)$ divisible by $2n$ ( Mod$[S(B),2n]=0$).

Example: $A(3)=\{ 1,2,3 \}$, so we have only two "special subset" - $\{\varnothing\}$ and $\{1,2,3\}$.

$A(5)=\{ 1,2,3,4,5 \}$, so we have $4$ "special subset" - $\{\varnothing\}, \{1,4,5\}, \{2,3,5\}, \{1,2,3,4\}$.

Let $F(n)$ is the number of all "special subsets" for $A(n)$, $n \in \mathbf{N}$.

I found for $n<50$ that $F(n)-1$ is the nearest integer to $\frac{2^{n-1}}{n}$. $F(n)$=Floor$[\frac{2^{n-1}}{n} + \frac{1}{2}] + 1$.

Is it possible to prove this formula for any natural $n$ -?

share|improve this question
    
Have you tried cranking out a proof by induction? –  Benjamin Dickman Nov 1 '12 at 1:28
    
Is it a hint? Or just a suggestion? I can't imagine how it may help us to count F(k+1) if we know F(k). –  Mike Nov 1 '12 at 1:51
add comment

1 Answer

up vote 3 down vote accepted

Let $B_j$ be independent Bernoulli random variables with parameter $1/2$, i.e. they take values $0$ and $1$, each with probability $1/2$, and $X = \sum_{j=1}^n j B_j$. Thus $X$ is the sum of a randomly-chosen subset of $A(n)$. Your $F(n) = 2^n P(X \equiv 0 \mod 2n) = \frac{2^n}{2n} \sum_{\omega} E[\omega^X]$ where the sum is over the $2n$'th roots of unity ($\omega = e^{\pi i k/n}, k=0,1,\ldots, 2n-1$). Now $$E[\omega^X] = \prod_{j=1}^n E[\omega^{j B_j}] = \prod_{j=1}^n \frac{1 + \omega^j}{2} $$ For $\omega = 1$ we have $E[1^X] = 1$, so this gives us a term $2^{n-1}/n$. Each $\omega \ne 1$ is a primitive $m$'th root of $1$, i.e. $\omega = e^{2\pi i k/m}$ where $m$ divides $2n$ and $\gcd(k,m)=1$. Now $E[\omega^X] = 0$ if some $\omega^j = -1$. This is true iff $m$ is even. Each primitive $m$'th root for the same $m$ gives the same value for $E[\omega^X]$ (the same factors appear, just in different orders). It appears to me (from looking at the first few cases) that if $\omega$ is a primitive $m$'th root with $m$ odd, $E[\omega^X] = 2^{-n+n/m}$. Now there are $\phi(m)$ primitive $m$'th roots, so I get $$ F(n) = \frac{2^{n-1}}{n} + \sum_m \frac{\phi(m)}{n} 2^{n/m-1} $$ where the sum is over all odd divisors of $n$ except $1$.

It's not true that $F(n) -1$ is the nearest integer to $2^{n-1}/n$, although $2^{n-1}/n$ is the largest term in $F(n)$. For example, $F(25) = 671092$ but $2^{25-1}/25 = 671088.64$.

share|improve this answer
    
It is very difficult to me (my poor level) to understand this decision. I need some time before I'll accept it. Thank you very much! –  Mike Nov 1 '12 at 5:00
    
See also oeis.org/A000016 and references there. –  Robert Israel Nov 1 '12 at 7:01
    
Hmm this would explain why I was getting contradictory results to the ones posted... I thought maybe I had made an error somehow because the question poser claimed he had checked up to 50. –  dinoboy Nov 1 '12 at 17:14
    
The equation $E[\omega^X] = 2^{-n+n/m}$ can be obtained from the identity $\sin(m\theta) = 2^{m-1} \prod_{j=0}^{m-1} \sin(\pi j/m + \theta)$ –  Robert Israel Nov 1 '12 at 19:20
add comment

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.