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

Answer: 401

Concepts:factorial Legendre’s Formula divisibility

Difficulty rating: 2840

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, $\begin{aligned} e_{2009} &= 1004 + 502 + 251 \\ &\quad {}+ 125 + 62 + 31 + 15 \\ &\quad {}+ 7 + 3 + 1 \\ &= 2001, \end{aligned}$ so $a = 2009 + 2001 = 4010.$ Then $\frac{ab}{10} = \frac{4010 \cdot 1}{10} = 401.$

2009 AIME II Problem 7

Answer: 401

Difficulty rating: 2840

Solution:

Problem 7 in Other Years