⚠️ We denounce the Israel's brutal massacre on the civilians, for Palestinian and Iran!

Lex Blog

2024, March, 05
Proof of Faulhaber's Formula

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

#mathematics

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.