Project Euler Problem 831
Let g(m) be the integer defined by the following double sum of products of binomial coefficients: You are given that g(1
Solution
Answer: 5226432553
We simplify the double sum using binomial identities.
Starting from
$$g(m)=\sum_{j=0}^m\sum_{i=0}^j(-1)^{j-i}\binom mj\binom ji\binom{j+5+6i}{j+5},$$
use
$$\binom mj\binom ji=\binom mi\binom{m-i}{j-i},$$
and let $k=j-i$. Then
$$g(m) = \sum_{i=0}^m \binom mi \sum_{k=0}^{m-i} (-1)^k \binom{m-i}{k} \binom{7i+k+5}{7i-m}.$$
Applying the alternating binomial identity
$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{k+r}{s} = (-1)^n\binom{r}{s-n},$$
gives
$$g(m) = \sum_{i=0}^{m} (-1)^{m-i} \binom mi \binom{7i+5}{m+5}.$$
This can be rewritten as a coefficient extraction:
$$g(m) = [x^{m+5}] (1+x)^5\left((1+x)^7-1\right)^m.$$
Since
$$(1+x)^7-1 = x\left(7+21x+35x^2+35x^3+21x^4+7x^5+x^6\right),$$
we only need the coefficient of $x^5$, so we can truncate to degree $5$ and exponentiate the degree-5 polynomial modulo $x^6$ using fast binary exponentiation. This computes $g(142857)$ exactly in under a second.
Writing the resulting integer in base $7$, the first ten digits are:
Answer: 5226432553