Faulhaber’s Formulas

The sum of the $k$th powers of the first $n$ positive integers can be expressed as a polynomial of degree $k+1$ with rational coefficients, the Faulhaber’s Formulas:
$1^k + 2^k + … + n^k = \sum_{i=1}^n i^k = \sum_{i=1}^{k+1} a_{i} n^i = a_{1} n + a_{2} n^2 + … + a_{k} n^k + a_{k+1} n^{k + 1}$,
where $a_i$’s are rational coefficients that can be written as reduced fractions $p_i/q_i$ (if $a_i = 0$, we shall consider $q_i = 1$).
For example, $1^4 + 2^4 + … + n^4 = -\frac 1 {30} n + \frac 1 3 n^3 + \frac 1 2 n^4 + \frac 1 5 n^5.$
Define $D(k)$ as the value of $q_1$ for the sum of $k$th powers (i.e. the denominator of the reduced fraction $a_1$).
Define $F(m)$ as the $m$th value of $k \ge 1$ for which $D(k) = 20010$.
You are given $D(4) = 30$ (since $a_1 = -1/30$), $D(308) = 20010$, $F(1) = 308$, $F(10) = 96404$.
Find $F(10^5)$.

Firstly, to solve this problem, we need to understand the nature of the denominator $a_1$. The formula is derived from the Bernoulli numbers. As in the example, the sum of $4$th powers is a polynomial and the coefficients are expressed in terms of Bernoulli numbers. For odd $k$ > 1, Bernoulli numbers and hence $a_1=0$. This is because Bernoulli numbers $B_{2k+1}$ for odd $k$ are zero in general.

Now, for even values of $k = 2m$, the denominator of $a_1$ that corresponds to those cases is ${(2m)!}$ over the denominator of $B_{2m}$. Remember here that Bernoulli number $B_{2m}$ is non-zero for even indices.

As a factor of $2$ is present in the numerator and denominator, we can cancel it out. Hence, ${(2m)!}$ turns into ${(2^m*m!)}$.

Furthermore, Bernoulli Numbers have integral numerators, we will be left with ${(2^m*m!)}$ over a product of powers of primes (excluding $2$).

As $m$ increases, more and more primes get included in the denominator since we keep multiplying by the next number while computing factorials. So if we want to find the value of $m$ where the denominator $D(k) = 20010 = 2 \times 3^3 \times 5 \times 23 \times 29$, we need to work our way up by increasing $m$ until all these prime factors are included.

Working out the numbers, we start with $m=2$, we get $2^2*2! = 2 \times 3$ (getting $2$ and one of the $3$s), at $m=3$ we get $2^3*3!=2^3\times2 \times 3$ (getting the $2 \times 2$ and a second $3$), then at $m=5$ we get $2^5*5!=2^5\times2\times3\times4\times5$ (getting the $5$), at $m=8$ we get $2^8*8!$ gaining a $2^3$ (which we don’t need) and a third $3$, at $m=23$ we get $2^{23}*23!$ gaining a lot more $2$s (which we don’t need) and the $23$, and finally, at $m=29$, we get $2^{29}*29!$ gaining the $29$ so that we have all the factors we need.

Therefore every $10$th multiple of $29$ is a solution to this problem. And hence $F(10^n) = 29 \times 10^n$. So $F(10^5) = 29 \times 10^5 = 2900000$.

More Answers: