Faulhaber's triangle

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.

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:

$\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