Problem 4

Prove that for every positive integer

t

there is a unique permutation

a_0,a_1,\ldots,a_{t-1}

0,1,\ldots,t-1

such that, for every

0\le i\le t-1

, the binomial coefficient

\binom{t+i}{2a_i}

is odd and

2a_i\neq t+i

Step 2 of 6: A bit-count identity

Previous step Next step

\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)|

Detailed analysis

Since $S(2i)=\{1+x:x\in S(i)\}$ and $S(2i+1)=\{0\}\cup\{1+x:x\in S(i)\}$ (appending a binary digit), a short induction on $t$ shows $\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)|$ : each step splits the sum over $t$ consecutive integers into a sum over $t$ smaller integers plus one extra set bit per pair $(2i,2i+1)$ .