Maths Olympiad Prep

Library / /279 of 520

Number theory Difficulty 7.0 National olympiad Prove it

For a positive integer ss, denote with v2(s)v_2(s) the maximum power of 22 that divides ss.
Prove that for any positive integer mm that: v2(n=12m(2nn))=m2m1+1.v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right)=m2^{m-1}+1.

(FYROM)

Solution

1. Lemma: ν2((2nn))\nu_2\left( \binom{2n}{n}\right) is equal to the number of 11's in the binary representation of nn.

2. Proof of Lemma: This is a direct application of Kummer's Theorem, which states that the power of a prime pp dividing a binomial coefficient (ab)\binom{a}{b} is equal to the number of carries when bb and aba-b are added in base pp. For p=2p=2, this translates to the number of 11's in the binary representation of nn.

3. Main Proof:
We need to prove that:
v2(n=12m(2nn))=m2m1+1. v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right)=m2^{m-1}+1.

4. Using the lemma, we have:
v2(n=12m(2nn))=n=12mv2((2nn)). v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right) = \sum_{n=1}^{2^m} v_2\left(\binom{2n}{n}\right).

5. According to the lemma, v2((2nn))v_2\left(\binom{2n}{n}\right) is the number of 11's in the binary representation of nn. Therefore, we need to sum the number of 11's in the binary representations of all integers from 11 to 2m2^m.

6. The number of 11's in the binary representation of numbers from 11 to 2m2^m can be calculated as follows:
- For each bit position kk (from 00 to m1m-1), there are 2m12^{m-1} numbers that have a 11 in that position.
- Therefore, the total number of 11's in the binary representations of numbers from 11 to 2m2^m is:
k=0m12m1=m2m1. \sum_{k=0}^{m-1} 2^{m-1} = m \cdot 2^{m-1}.

7. However, we need to account for the fact that 2m2^m itself has exactly one 11 in its binary representation, which adds an additional 11 to the sum.

8. Therefore, the total sum is:
n=12mv2((2nn))=m2m1+1. \sum_{n=1}^{2^m} v_2\left(\binom{2n}{n}\right) = m \cdot 2^{m-1} + 1.

9. Hence, we have:
v2(n=12m(2nn))=m2m1+1. v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right) = m \cdot 2^{m-1} + 1.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.