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:








∑

k
=
1


n



k

p


=


1

p
+
1




∑

j
=
0


p





(



p
+
1

j


)




B

j



n

p
+
1
−
j




{\displaystyle \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




{\displaystyle 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:






∑

k
=
1


n



k

2


=


1
6


n
+


1
2



n

2


+


1
3



n

3




{\displaystyle \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 18th row of Faulhaber's triangle, compute the sum: 




∑

k
=
1


1000



k

17




{\displaystyle \sum _{k=1}^{1000}k^{17}}

 (extra credit).
 See also

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


import algorithm, math, strutils
import bignum
 
type FaulhaberSequence = seq[Rat]
 
#---------------------------------------------------------------------------------------------------
 
func bernoulli(n: Natural): Rat =
  ## Return nth Bernoulli coefficient.
 
  var a = newSeq[Rat](n + 1)
  for m in 0..n:
    a[m] = newRat(1, m + 1)
    for k in countdown(m, 1):
      a[k - 1] = (a[k - 1] - a[k]) * k
  result = if n != 1: a[0] else: -a[0]
 
#---------------------------------------------------------------------------------------------------
 
func faulhaber(n: Natural): FaulhaberSequence =
  ## Return nth Faulhaber sequence (high degree first).
 
  var a = newRat(1, n + 1)
  var sign = -1
  for k in 0..n:
    sign = -sign
    result.add(a * sign * binom(n + 1, k) * bernoulli(k))
 
#---------------------------------------------------------------------------------------------------
 
proc display(fs: FaulhaberSequence) =
  ## Return the string representing a Faulhaber sequence.
 
  var str = ""
  for i, coeff in reversed(fs):
    str.addSep(" ", 0)
    str.add(($coeff).align(6))
  echo str
 
#---------------------------------------------------------------------------------------------------
 
func evaluate(fs: FaulhaberSequence; n: int): Rat =
  ## Evaluate the polynomial associated to a sequence for value "n".
 
  result = newRat(0)
  for coeff in fs:
    result = result * n + coeff
  result *= n
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
for n in 0..9:
  display(faulhaber(n))
 
echo ""
let fs18 = faulhaber(17)  # 18th row.
echo fs18.evaluate(1000)