user
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 {\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 {\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 {\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 {\displaystyle \sum \_{k=1}^{1000}k^{17}}}
       (extra credit).

See also

* Bernoulli numbers
* Evaluate binomial coefficients
* Faulhaber's formula (Wikipedia)
* Faulhaber's triangle (PDF)
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2017.05

**Translation of**: Sidef

```
# Helper subs

sub infix:<reduce> (\prev, \this) { this.key => this.key * (this.value - prev.value) }

sub next-bernoulli ( (:key($pm), :value(@pa)) ) {
    $pm + 1 => [ map *.value, [\reduce] ($pm + 2 ... 1) Z=> 1 / ($pm + 2), |@pa ]
}

constant bernoulli = (0 => [1.FatRat], &next-bernoulli ... *).map: { .value[*-1] };

sub binomial (Int $n, Int $p) { combinations($n, $p).elems }

sub asRat (FatRat $r) { $r ?? $r.denominator == 1 ?? $r.numerator !! $r.nude.join('/') !! 0 }


# The task
sub faulhaber_triangle ($p) { map { binomial($p + 1, $_) * bernoulli[$_] / ($p + 1) }, ($p ... 0) }

# First 10 rows of Faulhaber's triangle:
say faulhaber_triangle($_)».&asRat.fmt('%5s') for ^10;
say '';

# Extra credit:
my $p = 17;
my $n = 1000;
say sum faulhaber_triangle($p).kv.map: { $^value * $n**($^key + 1) }

```

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
```