2020 CIME I Problems/Problem 7

Problem 7

For every positive integer $n$ , define $f(n)=\frac{n}{1 \cdot 3 \cdot 5 \cdots (2n+1)}.$ Suppose that the sum $f(1)+f(2)+\cdots+f(2020)$ can be expressed as $\frac{p}{q}$ for relatively prime integers $p$ and $q$ . Find the remainder when $p$ is divided by $1000$ .

Solution

Let $S(n) = f(1)+f(2)+\cdots+f(n)$ . We claim that $S(n) = \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!}.$ We show this using induction. Suppose this is true for some $n = k$ . Then, it must be true for $k+1$ . The base case when $k = 1$ is trivial. Then, we have that $\begin{align*} S(k+1) &= f(k) + S(k) \\ {} &= \frac{n}{(2n+1)!!} + \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!} \\ {} &= \frac{1}{2} - \frac{1}{2 \cdot (2n+3)!!}. \end{align*}$ Hence, this completes the induction therefore proving the claim. So, the numerator $p$ is $\frac{1}{2}(4041!! - 1)$ . We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that $4041!! \equiv 0 \pmod{125}$ so $p \equiv 62\pmod{125}$ . Also, instead of considering $p$ modulo $8$ , we consider it modulo $16$ . Then, we get $4041!! \equiv 3^{253} \cdot 5^{253} \cdot 7^{253} \cdot 9^{252} \cdot 11^{252} \cdot 13^{252} \cdot 15^{252} \equiv 3 \cdot 5 \cdot 7 \cdot 9 \equiv 1\pmod{16},$ by Euler's Totient Theorem as $\phi(16) = 8$ . This implies that $\frac{1}{2}(4041!! - 1) \equiv 0\pmod{8}$ , so $p \equiv 0\pmod{8}$ . Solving the system of congruences, we get $p \equiv \boxed{312}\pmod{1000}$ . ~rocketsri (based off of official solution)

2020 CIME I (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 CIME Problems and Solutions

Page

Toolbox

Search

2020 CIME I Problems/Problem 7

Problem 7

Solution

See also