NOTE & BLOG

    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,p∈Z>0n, p \in \mathbb{Z}_{>0} be (strictly) positive integers.

    Then:

    ∑k=1nkp=1p+1∑i=0p(−1)i(p+1i)Binp+1−i=np+1p+1−B1⋅np1!+B2⋅p⋅np−12!+B4⋅p⋅(p−1)⋅(p−2)⋅np−34!+⋯\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 x≥0x \ge 0.

    ∑k=0n−1ekx=∑k=0n−1∑p=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=0n−1kp)xpp!= \sum_{p = 0}^\infty \left(\sum_{k = 0}^{n - 1} k^p\right) \frac{x^p}{p!}

    We also have:

    ∑k=0n−1ekx=1−enx1−ex\sum_{k = 0}^{n - 1} e^{k x} = \frac{1 - e^{n x}}{1 - e^x}

    Sum of Geometric Sequence

    =enx−1xxex−1= \frac{e^{n x} - 1}{x} \frac{x}{e^x - 1}

    multiplying numerator and denominator by xx

    =1x(∑p=0∞(nx)pp!−1)∑p=0∞Bpxpp!= \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=0∞Bpxpp!= \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=0∞Bpxpp!= \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=0∞np+1xp(p+1)!∑p=0∞Bpxpp!= \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=0∞∑i=0pnp+1−ixp−i(p+1−i)!i!Binp+1−ixp= \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+1∑i=0p(p+1i)Binp+1−i)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=0n−1kp=1p+1∑i=0p(p+1i)Binp+1−i\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+1∑i=0p(−1)i(p+1i)Binp+1−i\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=0n−1kp=1p+1∑i=0p(p+1i)Binp+1−i\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=0n−1kp+np=1p+1∑i=0p(p+1i)Binp+1−i+(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+1∑i=0p(−1)i(p+1i)Binp+1−i\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.

    # MATHEMATICS