Lizzie writes a list of fractions as follows. First, she writes $\frac{1}{1}$ , the only fraction whose numerator and denominator add to $2$. Then she writes the two fractions whose numerator and denominator add to $3$, in increasing order of denominator. Then she writes the three fractions whose numerator and denominator sum to 4 in increasing order of denominator. She continues in this way until she has written all the fractions whose numerator and denominator sum to at most $1000$. So Lizzie’s list looks like: $$\frac{1}{1}, \frac{2}{1} , \frac{1}{2} , \frac{3}{1} , \frac{2}{2}, \frac{1}{3}, \frac{4}{1}, \frac{3}{2} , \frac{2}{3}, \frac{1}{4} ,\cdots, \frac{1}{999}$$
Let $p_k$ be the product of the first $k$ fractions in Lizzie’s list. Find, with proof, the value of $p_1 + p_2 +\cdots+ p_{499500}$.
The list can be divided into different groups based on the sum of the numerator and denominator. $$\underbrace{\frac{1}{1}}_{group\ 2}, \underbrace{\frac{2}{1}, \frac{1}{2}}_{group\ 3}, \underbrace{\frac{3}{1}, \frac{2}{2}, \frac{1}{3}}_{group\ 3}, \underbrace{\frac{4}{1},\frac{3}{2},\frac{2}{3},\frac{1}{4}}_{group\ 4}, \cdots$$
There are $(n-1)$ elements in group $n$. Their denominators increase from $1$ to $(n-1)$. Their numerators decrease from $(n-1)$ to $1$. Therefore, the product of all elements in any given group is $1$. This means that if $p_k$ is a multiple of terms in more than one group, only those in the last groups need to be considered.
Meanwhile, in group $n$, the product of the first $1\le m\le (n-1)$ elements is equal to.$$\frac{(n-1)\cdot(n-2)\cdots(n-m)}{1\cdot 2 \cdots m} = \binom{n-1}{m}$$
It follows that the sum of all the $p_k$ associated with group $n$ equals $$\binom{n-1}{1} + \binom{n-1}{2} + \cdots + \binom{n-1}{n-1} = 2^{n-1} - 1$$
Therefore the desired sum is $$\begin{array}{rl} &(2^1-1) + (2^2-1) +\cdots + (2^{999} - 1)\\ = & (2^1 + 2^2+ \cdots + 2^{999}) - 999\\ = & (2^0 + 2^1 + 2^2+ \cdots + 2^{999}) - 1000\\ = & 2^{1000} - 1 - 1000\\ = & \boxed{2^{1000} - 1001} \end{array}$$