Difference between revisions of "2009 AIME II Problems/Problem 7"
m (→Solution) |
m (→Solution) |
||
Line 6: | Line 6: | ||
First, note that <math>(2n)!! = 2^n \cdot n!</math>, and that <math>(2n)!! \cdot (2n-1)!! = (2n)!</math>. | First, note that <math>(2n)!! = 2^n \cdot n!</math>, and that <math>(2n)!! \cdot (2n-1)!! = (2n)!</math>. | ||
− | We can now take the fraction <math>\dfrac{(2i-1)!!}{(2i)!!}</math> and multiply both the numerator and the | + | We can now take the fraction <math>\dfrac{(2i-1)!!}{(2i)!!}</math> and multiply both the numerator and the denominator by <math>(2i)!!</math>. We get that this fraction is equal to <math>\dfrac{(2i)!}{(2i)!!^2} = \dfrac{(2i)!}{2^{2i}(i!)^2}</math>. |
Now we can recognize that <math>\dfrac{(2i)!}{(i!)^2}</math> is simply <math>{2i \choose i}</math>, hence this fraction is <math>\dfrac{{2i\choose i}}{2^{2i}}</math>, and our sum turns into <math>S=\sum_{i=1}^{2009} \dfrac{{2i\choose i}}{2^{2i}}</math>. | Now we can recognize that <math>\dfrac{(2i)!}{(i!)^2}</math> is simply <math>{2i \choose i}</math>, hence this fraction is <math>\dfrac{{2i\choose i}}{2^{2i}}</math>, and our sum turns into <math>S=\sum_{i=1}^{2009} \dfrac{{2i\choose i}}{2^{2i}}</math>. |
Revision as of 20:12, 23 March 2015
Problem
Define to be for odd and for even. When is expressed as a fraction in lowest terms, its denominator is with odd. Find .
Solution
First, note that , and that .
We can now take the fraction and multiply both the numerator and the denominator by . We get that this fraction is equal to .
Now we can recognize that is simply , hence this fraction is , and our sum turns into .
Let . Obviously is an integer, and can be written as . Hence if is expressed as a fraction in lowest terms, its denominator will be of the form for some .
In other words, we just showed that . To determine , we need to determine the largest power of that divides .
Let be the largest such that that divides .
We can now return to the observation that . Together with the obvious fact that is odd, we get that .
It immediately follows that , and hence .
Obviously, for the function is is a strictly decreasing function. Therefore .
We can now compute . Hence .
And thus we have , and the answer is .
See Also
2009 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.