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.

Prove that for all $k \geq 1$ and $n \geq 2 ^{k-1}$, the number of subsets of $\{1,2,3\cdots n\}$ with sum congruent to $i$ mod $2^k$, equals the number with sum congruent to $i+1$ mod $2^k$, for all $0\leq i\lt2^k$.

P.S.

i do not know the math around it, but this is how the number of subsets with sum congruent to $i$ mod $2^k$ behaves for different values of $n$. The header row column values indicate the sum congruent to $i$ mod $2^k$ values. In each row, the first column indicates the value of $n$.

In this example, $k = 3,2^k=8$ and $n$ varies from $1$ to $6$

       0 1 2 3 4 5 6 7

    1  1 1 0 0 0 0 0 0 
    2  1 1 1 1 0 0 0 0  
    3  1 1 1 2 1 1 1 0 
    4  2 2 2 2 2 2 2 2 
    5  4 4 4 4 4 4 4 4 
    6  8 8 8 8 8 8 8 8

Th table is constructed using the recurrence relation, $S_{n,i} = S_{n-1,i} + S_{n-1,(i-n) mod 2^k}$, if we assume $S_{n,i}$ is the number of subsets of $\{1,2,3 \cdots n\}$ with sum congruent to $i$ mod $2^k$. From the table, we can observe that for $n\geq4$ i.e. $2^{k-1}$, all the entries of the row are equal. And if we look closely, each entry is $2^{n - k}$

share|improve this question

1 Answer 1

Hint: Prove it for $n = 2^{k-1}$ by using $$(1+x)(1+x^2)(1+x^3)...(1+x^{2^{k-1}}) \pmod{x^{2^k} - 1}$$ and showing it is equivalent to $2^{2^{k-1} - k}(1 + x + ... + x^{2^k-1})$ via plugging in the $2^{k}$th roots of unity. Then apply induction to get the desired result, $n = 2^{k-1}$ being your base case.

share|improve this answer
    
Thank you for responding. But, i do not know how to do it. –  Novice Feb 17 '13 at 13:03
    
Which part do you not know how to do? The base case or the inductive step? –  dinoboy Feb 17 '13 at 19:23
    
Please help me understand the base case. Thanks. –  Novice Feb 18 '13 at 18:12

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.