Question

Define $n!!$ to be $n(n-2)(n-4)\cdots 3 \cdot 1$ for $n$ odd and $n(n-2)(n-4)\cdots 4 \cdot 2$ for $n$ even. When $\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}$ is expressed as a fraction in lowest terms, its denominator is $2^a b$ with $b$ odd. Find $\frac{ab}{10}.$

Answer

Solution:

The $i$ th term is $\frac{(2i-1)!!}{(2i)!!}$ with odd numerator, and $(2i)!! = 2^i \cdot i!.$ Because $\binom{2i}{i} = \frac{(2i)!}{i!\,i!} = \frac{2^i (2i-1)!!}{i!}$ is an integer, every odd prime power dividing $i!$ also divides $(2i-1)!!.$ Hence in lowest terms the $i$ th term has denominator exactly $2^{a_i}$ where $a_i = i + e_i$ and $e_i$ is the exponent of $2$ in $i!.$ The $a_i$ strictly increase, so over the common denominator $2^{a_{2009}}$ every term except the last contributes an even numerator while the last contributes an odd one. The sum in lowest terms therefore has denominator exactly $2^{a_{2009}},$ so $b = 1.$

By Legendre's formula, $e_{2009} = 1004 + 502 + 251 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 2001,$ so $a = 2009 + 2001 = 4010.$ Then $\frac{ab}{10} = \frac{4010 \cdot 1}{10} = 401.$

2009 AIME II Problem 7

Solution:

Problem 7 in Other Years