Faulhaber's triangle

Named after Johann Faulhaber, the rows of Faulhaber's triangle are the coefficients of polynomials that represent sums of integer powers, which are extracted from Faulhaber's formula:

Faulhaber's triangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

$\sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}$

where $B_{n}$ is the nth-Bernoulli number.

The first 5 rows of Faulhaber's triangle, are:

    1
  1/2  1/2
  1/6  1/2  1/3
    0  1/4  1/2  1/4
-1/30    0  1/3  1/2  1/5

Using the third row of the triangle, we have:

$\sum _{k=1}^{n}k^{2}={1 \over 6}n+{1 \over 2}n^{2}+{1 \over 3}n^{3}$

Task

• show the first 10 rows of Faulhaber's triangle.
• using the 17th row of Faulhaber's triangle, compute the sum: $\sum _{k=1}^{1000}k^{17}$ (extra credit).

See also

• Bernoulli numbers
• Evaluate binomial coefficients
• Faulhaber's formula (Wikipedia)
• Faulhaber's triangle (PDF)

Sidef

<lang ruby>func faulhaber_triangle(p) {

   gather {
       for j in (p+1 ^.. 0) {
           take(binomial(p+1, j) * bernoulli(j) / (p+1))
       }
   }

}

1. 1. First 10 rows of Faulhaber's triangle:

for p in (0 .. 9) {

   say faulhaber_triangle(p).map{ '%6s' % .as_rat }.join

}

1. 1. Extra credit:

const p = 17 const n = 1000

say say faulhaber_triangle(p).map_kv{|k,v| v * n**(k+1) }.sum</lang>

Output:

     1
   1/2   1/2
   1/6   1/2   1/3
     0   1/4   1/2   1/4
 -1/30     0   1/3   1/2   1/5
     0 -1/12     0  5/12   1/2   1/6
  1/42     0  -1/6     0   1/2   1/2   1/7
     0  1/12     0 -7/24     0  7/12   1/2   1/8
 -1/30     0   2/9     0 -7/15     0   2/3   1/2   1/9
     0 -3/20     0   1/2     0 -7/10     0   3/4   1/2  1/10

56056972216555580111030077961944183400198333273050000