Proof of Faulhaber's Formula

    Mar 5, 2024

    Faulhaber's Formula, which provides a method to compute the sum of the p-th powers of the first n positive integers.

    Theorem

    Let n,pZ>0n, p \in \mathbb{Z}_{>0} be (strictly) positive integers.

    Then:

    k=1nkp=1p+1i=0p(1)i(p+1i)Binp+1i=np+1p+1B1np1!+B2pnp12!+B4p(p1)(p2)np34!+\sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i} \\ = \frac{n^{p + 1}}{p + 1} - \frac{B_1 \cdot n^p}{1!} + \frac{B_2 \cdot p \cdot n^{p - 1}}{2!} + \frac{B_4 \cdot p \cdot (p - 1) \cdot (p - 2) \cdot n^{p - 3}}{4!} + \cdots

    where:

    • BiB_i denotes the iith Bernoulli number.

    Proof

    Let x0x \ge 0.

    k=0n1ekx=k=0n1p=0(kx)pp!\sum_{k = 0}^{n - 1} e^{k x} = \sum_{k = 0}^{n - 1} \sum_{p = 0}^\infty \frac{(k x)^p}{p!} =p=0(k=0n1kp)xpp!= \sum_{p = 0}^\infty \left(\sum_{k = 0}^{n - 1} k^p\right) \frac{x^p}{p!}

    We also have:

    k=0n1ekx=1enx1ex\sum_{k = 0}^{n - 1} e^{k x} = \frac{1 - e^{n x}}{1 - e^x}

    Sum of Geometric Sequence

    =enx1xxex1= \frac{e^{n x} - 1}{x} \frac{x}{e^x - 1}

    multiplying numerator and denominator by xx

    =1x(p=0(nx)pp!1)p=0Bpxpp!= \frac{1}{x} \left(\sum_{p = 0}^\infty \frac{(n x)^p}{p!} - 1\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}

    Definition of Bernoulli Numbers and Power Series Expansion for Exponential Function

    =1x(p=1(nx)pp!)p=0Bpxpp!= \frac{1}{x} \left(\sum_{p = 1}^\infty \frac{(n x)^p}{p!}\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}

    Factorial of 00 and Zeroth Power

    =1x(p=0(nx)p+1(p+1)!)p=0Bpxpp!= \frac{1}{x} \left(\sum_{p = 0}^\infty \frac{(n x)^{p + 1}}{(p + 1)!}\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}

    Translation of Index Variable of Summation

    =p=0np+1xp(p+1)!p=0Bpxpp!= \sum_{p = 0}^\infty \frac{n^{p + 1} x^p}{(p + 1)!} \sum_{p = 0}^\infty \frac{B_p x^p}{p!}

    Power of Product

    =p=0i=0pnp+1ixpi(p+1i)!i!Binp+1ixp= \sum_{p = 0}^\infty \sum_{i = 0}^p \frac{n^{p + 1 - i} x^{p - i}}{(p + 1 - i)! i!} B_i n^{p + 1 - i} x^p

    Definition of Cauchy Product

    =p=0(1p+1i=0p(p+1i)Binp+1i)xpp!= \sum_{p = 0}^\infty \left(\frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}\right) \frac{x^p}{p!}

    multiplying by 11 and Product of Powers

    k=0n1kp=1p+1i=0p(p+1i)Binp+1i\sum_{k = 0}^{n - 1} k^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}

    Definition of Binomial Coefficient

        k=1nkp=1p+1i=0p(1)i(p+1i)Binp+1i\implies \sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i}

    Equating coefficients:

    k=0n1kp=1p+1i=0p(p+1i)Binp+1i\sum_{k = 0}^{n - 1} k^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}     k=0n1kp+np=1p+1i=0p(p+1i)Binp+1i+(1p+1(p+11)np)\implies \sum_{k = 0}^{n - 1} k^p + n^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i} + \left(\frac{1}{p + 1} \binom{p + 1}{1} n^p\right)

    adding npn^{p} to both sides and Binomial Coefficient with One

        k=1nkp=1p+1i=0p(1)i(p+1i)Binp+1i\implies \sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i}

    as B1=12B_{1}=-\frac{1}{2} and Odd Bernoulli Numbers Vanish

    Q.E.D.