Central binomial coefficients: locating the extra 2-adic cancellation

n7_coffee·May 10, 2026(edited)

Legendre's formula gives the valuation of each binomial coefficient, but not the valuation of their difference. Is there a way to expose the cancellation before applying valuations? Problem: For every integer

k \geq 2

, prove that

2^{3k}

divides the number

\binom{2^{k+1}}{2^{k}} - \binom{2^{k}}{2^{k-1}}

Source: IMO 2007 Shortlist · MNET-06PR

Open MNET-06PR in the question bank →

5 replies

crimsonFlask·May 12, 2026(edited)

Set

m=2^k

and separate odd and even factors. The difference equals a rational prefactor of 2-adic valuation 1 times

P(m)

, where

P(X)=\prod_{j<m,\ j\text{ odd}}(X+j)-\prod_{j<m,\ j\text{ odd}}(X-j)

n7_coffee·May 12, 2026(edited)

There are an even number of factors because k≥2, so P is odd. Then

P(X)=cX+X^3Q(X)

. This isolates the coefficient that matters.

crimsonFlask·May 12, 2026(edited)

Yes. The linear coefficient is

c=2(m-1)!!\sum_{j<m,\ j\text{ odd}}1/j

. Pair j with m−j to pull out a factor m. The rest reduces modulo m to an odd unit times the sum of squares of the odd residues.

no_mp_left·May 12, 2026(edited)

Inversion permutes the odd residues modulo

2^k

, so the inverse-square sum has the same residue as their square sum. The latter is

2^{k-1}(2^{2k}-1)/3

, with valuation k−1.

n7_coffee·May 13, 2026(edited)

Then c should have valuation 2k−1, so c·m has valuation 3k−1 and the cubic part has at least 3k. Together with the prefactor that gives exactly 3k. I still want to write out the odd-denominator bookkeeping rather than silently treat the prefactor as an integer.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

Central binomial coefficients: locating the extra 2-adic cancellation

n7_coffee·May 10, 2026(edited)

k \geq 2

, prove that

2^{3k}

divides the number

\binom{2^{k+1}}{2^{k}} - \binom{2^{k}}{2^{k-1}}

Source: IMO 2007 Shortlist · MNET-06PR

Open MNET-06PR in the question bank →

5 replies

crimsonFlask·May 12, 2026(edited)

Set

m=2^k

and separate odd and even factors. The difference equals a rational prefactor of 2-adic valuation 1 times

P(m)

, where

P(X)=\prod_{j<m,\ j\text{ odd}}(X+j)-\prod_{j<m,\ j\text{ odd}}(X-j)

n7_coffee·May 12, 2026(edited)

There are an even number of factors because k≥2, so P is odd. Then

P(X)=cX+X^3Q(X)

. This isolates the coefficient that matters.

crimsonFlask·May 12, 2026(edited)

Yes. The linear coefficient is

c=2(m-1)!!\sum_{j<m,\ j\text{ odd}}1/j

. Pair j with m−j to pull out a factor m. The rest reduces modulo m to an odd unit times the sum of squares of the odd residues.

no_mp_left·May 12, 2026(edited)

Inversion permutes the odd residues modulo

2^k

, so the inverse-square sum has the same residue as their square sum. The latter is

2^{k-1}(2^{2k}-1)/3

, with valuation k−1.

n7_coffee·May 13, 2026(edited)