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 6 of 6: Induction builds the unique pairing

Previous step Next step

\exists!\text{ pairing of small and big numbers}\implies\exists!\ (a_0,\ldots,a_{t-1})

Detailed analysis

One shows by induction on $t$ that the small numbers $\{0,\ldots,\lceil t/2\rceil-1\}$ can be uniquely paired with the big numbers $\{\lceil t/2\rceil,\ldots,t-1\}$ so that each small $x$ satisfies $S(x)\subsetneq S(y)$ , $|S(x)|=|S(y)|-1$ , for its paired big $y$ : remove the unique power of two $2^a$ in the big range, forcing $2^a$ to pair with $2^a-2^a=0$ ; the remaining numbers split into two smaller matching problems joined by the bijection $z\mapsto 2^a-1-z$ , which is unique by the inductive hypothesis. Combined with the direct formula for odd $t+i$ , this yields the unique permutation $a_0,\ldots,a_{t-1}$ required by the problem.