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

Lex Blog

2024, April, 23
The Introduction to Bernoulli Number

Introduction, derivation and proof of Bernoulli numbers

#mathematics

Today, we mainly write about some problems related to combinatorial mathematics.

The Bernoulli numbers, denoted as BnB_n, are a sequence of rational numbers closely related to number theory. They appear in expressions for sums of powers of consecutive integers and have various applications in mathematics, including number theory, combinatorics, and calculus.

Bernoulli Numbers

The Bernoulli numbers, denoted as BnB_n, form a rational number sequence closely related to number theory. The first few discovered Bernoulli numbers are:

B0=1,B1=−12,B2=16,B3=0,B4=−130,…B_0 = 1, \quad B_1 = -\frac{1}{2}, \quad B_2 = \frac{1}{6}, \quad B_3 = 0, \quad B_4 = -\frac{1}{30}, \quad \dots

Sums of Equal Powers

The Bernoulli numbers are named after Jacob Bernoulli, who discovered remarkable relationships while investigating the formulas for sums of mmth powers. Let's denote

Sm(n)=∑k=0n−1km=0m+1m+⋯+(n−1)mS_{m}(n) = \sum_{k=0}^{n-1} k^m = 0^m + 1^m + \dots + (n-1)^m

Bernoulli observed the following sequence of formulas, outlining a pattern:

S0(n)=nS1(n)=12n2−12nS2(n)=13n3−12n2+16nS3(n)=14n4−12n3+14n2S4(n)=15n5−12n4+13n3−130n\begin{align*} S_0(n) &= n \\ S_1(n) &= \frac{1}{2}n^2 - \frac{1}{2}n \\ S_2(n) &= \frac{1}{3}n^3 - \frac{1}{2}n^2 + \frac{1}{6}n \\ S_3(n) &= \frac{1}{4}n^4 - \frac{1}{2}n^3 + \frac{1}{4}n^2 \\ S_4(n) &= \frac{1}{5}n^5 - \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n \end{align*}

It can be observed that in Sm(n)S_m(n), the coefficient of nm+1n^{m+1} is always 1m+1\frac{1}{m+1}, the coefficient of nmn^m is always −12-\frac{1}{2}, the coefficient of nm−1n^{m-1} is always m12\frac{m}{12}, the coefficient of nm−3n^{m-3} is always −m(m−1)(m−2)720-\frac{m(m-1)(m-2)}{720}, and the coefficient of nm−4n^{m-4} is always zero.

Moreover, the coefficient of nm−kn^{m-k} is always a constant times mk‾m^{\underline{k}}, where mk‾m^{\underline{k}} denotes the falling factorial power, i.e., m!(m−k)!\frac{m!}{(m-k)!}.

Recurrence Formula

Sm(n)=1m+1(B0nm+1+(m+11)B1nm+⋯+(m+1m)Bmn)=1m+1∑k=0m(m+1k)Bknm+1−k\begin{align*} S_m{(n)} &= \frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1 n^m+\dots+\binom{m+1}{m}B_m n) \\ &= \frac{1}{m+1}\sum_{k=0}^{m}\binom{m+1}{k}B_kn^{m+1-k} \end{align*}

The Bernoulli numbers are defined by the implicit recurrence relation:

∑j=0m(m+1j)Bj=0,(m>0)B0=1\begin{align*} \sum_{j=0}^{m}\binom{m+1}{j}B_j &= 0, \quad (m>0) \\ B_0 &= 1 \end{align*}

For example, (20)B0+(21)B1=0\binom{2}{0}B_0+\binom{2}{1}B_1=0. The first few values are:

n012345678…Bn1−12160−13001420−130…\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ \hline B_n & 1 & -\frac{1}{2} & \frac{1}{6} & 0 & -\frac{1}{30} & 0 & \frac{1}{42} & 0 & -\frac{1}{30} & \dots \\ \hline \end{array}

Proof

Proof by Induction

This proof method is adapted from Concrete Mathematics 6.5 BERNOULLI NUMBER.

Using binomial coefficient identities and induction:

Sm+1(n)+nm+1=∑k=0n−1(k+1)m+1=∑k=0n−1∑j=0m+1(m+1j)kj=∑j=0m+1(m+1j)Sj(n)\begin{align*} S_{m+1}(n)+n^{m+1} &= \sum_{k=0}^{n-1}(k+1)^{m+1} \\ &= \sum_{k=0}^{n-1}\sum_{j=0}^{m+1}\binom{m+1}{j}k^j \\ &= \sum_{j=0}^{m+1}\binom{m+1}{j}S_j(n) \end{align*}

Let S^m(n)=1m+1∑k=0m(m+1k)Bknm+1−k\hat{S}_{m}(n)=\frac{1}{m+1} \sum_{k=0}^{m} \binom{m+1}{k}B_kn^{m+1-k}, we want to prove Sm(n)=S^m(n)S_m(n)=\hat{S}_m(n). Assume that for j∈[0,m)j\in[0,m), Sj(n)=S^j(n)S_j(n)=\hat{S}_j(n).

Subtracting Sm+1(n)S_{m+1}(n) from both sides:

Sm+1(n)+nm+1=∑j=0m+1(m+1j)Sj(n)nm+1=∑j=0m(m+1j)Sj(n)=∑j=0m−1(m+1j)S^j(n)+(m+1m)Sm(n)\begin{align*} S_{m+1}(n)+n^{m+1} &=\sum_{j=0}^{m+1}\binom{m+1}{j}S_j(n) \\ n^{m+1} &=\sum_{j=0}^{m}\binom{m+1}{j}S_j(n) \\ &=\sum_{j=0}^{m-1}\binom{m+1}{j}\hat{S}_j(n)+\binom{m+1}{m}S_m(n) \end{align*}

By adding (m+1m)S^m(n)−(m+1m)S^m(n)\binom{m+1}{m}\hat{S}_m(n)-\binom{m+1}{m}\hat{S}_m(n) and simplifying:

nm+1=∑k=0mnk+1k+1∑j=km(m+1j)(jk)Bj−k+(m+1)Δ\begin{align*} n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\sum_{j=k}^{m}\binom{m+1}{j}\binom{j}{k}B_{j-k}+(m+1)\Delta \end{align*}

Let Δ=Sm(n)−S^m(n)\Delta = S_m(n)-\hat{S}_m(n), and expand S^j(n)\hat{S}_j(n):

nm+1=∑k=0mnk+1k+1∑j=km(m+1j)(jk)Bj−k+(m+1)Δ=∑k=0mnk+1k+1(m+1k)∑j=km(m−k+1j−k)Bj−k+(m+1)Δ\begin{align*} n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\sum_{j=k}^{m }\binom{m+1}{j}\binom{j}{k}B_{j-k}+(m+1)\Delta\\ &=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=k}^{m}\binom{m-k+1}{j-k}B_{j-k}+(m+1)\Delta\\ \end{align*}

Change the order of summation and apply binomial coefficient identity:

nm+1=∑k=0mnk+1k+1(m+1k)∑j=0m−k(m−k+1j)Bj+(m+1)Δ\begin{align*} n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=0}^{m-k}\binom{m-k+1}{j}B_{j}+(m+1)\Delta \end{align*}

Using the recursion relation:

∑j=0m(m+1j)Bj=0,(m>0)B0=1∑j=0m(m+1j)Bj=[m=0]\begin{align*} \sum_{j=0}^{m}\binom{m+1}{j}B_j &= 0, \quad (m>0) \\ B_0 &= 1 \\ \sum_{j=0}^{m}\binom{m+1}{j}B_j &= [m = 0] \end{align*}

Substituting:

nm+1=∑k=0mnk+1k+1(m+1k)[m−k=0]+(m+1)Δ=∑k=0mnk+1k+1(m+1k)+(m+1)Δ=nm+1m+1(m+1m)+(m+1)Δ=nm+1+(m+1)Δ\begin{align*} n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}[m - k = 0]+(m+1)\Delta\\ &=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}+(m+1)\Delta\\ &=\frac{n^{m+1}}{m+1}\binom{m+1}{m}+(m+1)\Delta\\ &=n^{m+1}+(m+1)\Delta \end{align*}

Thus, Δ=0\Delta=0, and Sm(n)=S^m(n)S_m(n)=\hat{S}_m(n).

Proof Using Exponential Generating Functions

For the recurrence ∑j=0m(m+1j)Bj=[m=0]\sum_{j=0}^{m}\binom{m+1}{j}B_j=[m=0],

adding Bm+1B_{m + 1} to both sides:

∑j=0m+1(m+1j)Bj=[m=0]+Bm+1∑j=0m(mj)Bj=[m=1]+Bm∑j=0mBjj!⋅1(m−j)!=[m=1]+Bmm!\begin{align*} \sum_{j=0}^{m+1}\binom{m+1}{j}B_j&=[m=0]+B_{m+1}\\ \sum_{j=0}^{m}\binom{m}{j}B_j&=[m=1]+B_{m}\\ \sum_{j=0}^{m}\dfrac{B_j}{j!}\cdot\dfrac{1}{(m-j)!}&=[m=1]+\dfrac{B_{m}}{m!} \end{align*}

Let B(z)=∑i≥0Bii!ziB(z) = \sum\limits_{i\ge 0}\dfrac{B_i}{i!}z^i, notice the left side is in convolution form, thus:

B(z)ez=z+B(z)B(z)=zez−1\begin{align*} B(z)\mathrm{e}^z &= z+B(z)\\ B(z)&=\dfrac{z}{\mathrm{e}^z - 1} \end{align*}

Let Fn(z)=∑m≥0Sm(n)m!zmF_n(z) = \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m, then:

Fn(z)=∑m≥0Sm(n)m!zm=∑m≥0∑i=0n−1imzmm!\begin{align*} F_n(z) &= \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m\\ &= \sum_{m\ge 0}\sum_{i=0}^{n-1}\dfrac{i^mz^m}{m!}\\ \end{align*}

Changing the order of summation:

Fn(z)=∑i=0n−1∑m≥0imzmm!=∑i=0n−1eiz=enz−1ez−1=zez−1⋅enz−1z\begin{align*} F_n(z) &=\sum_{i=0}^{n-1}\sum_{m\ge 0}\dfrac{i^mz^m}{m!}\\ &=\sum_{i=0}^{n-1}\mathrm{e}^{iz}\\ &=\dfrac{\mathrm{e}^{nz} - 1}{\mathrm{e}^z - 1}\\ &=\dfrac{z}{\mathrm{e}^z - 1}\cdot\dfrac{\mathrm{e}^{nz} - 1}{z} \end{align*}

Substituting B(z)=zez−1B(z)=\dfrac{z}{\mathrm{e}^z - 1}:

Fn(z)=B(z)⋅enz−1z=(∑i≥0Bii!)(∑i≥1nizi−1i!)=(∑i≥0Bii!)(∑i≥0ni+1zi(i+1)!)\begin{align*} F_n(z) &= B(z)\cdot\dfrac{\mathrm{e}^{nz} - 1}{z}\\ &= \left(\sum_{i\ge 0}\dfrac{B_i}{i!} \right)\left(\sum_{i\ge 1}\dfrac{n^i z^{i - 1}}{i!}\right)\\ &= \left(\sum_{i\ge 0}\dfrac{B_i}{i!} \right)\left(\sum_{i\ge 0}\dfrac{n^{i+1} z^{i}}{(i+1)!}\right) \end{align*}

As Fn(z)=∑m≥0Sm(n)m!zmF_n(z) = \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m, i.e., Sm(n)=m![zm]Fn(z)S_m(n)=m![z^m]F_n(z):

Sm(n)=m![zm]Fn(z)=m!∑i=0mB×ii!⋅nm−i+1(m−i+1)!=1m+1∑i=0m(m+1i)Binm−i+1\begin{align*} S_m(n)&=m![z^m]F_n(z)\\ &= m!\sum_{i=0}^{m}\dfrac{B \times i}{i!}\cdot\dfrac{n^{m-i+1}}{(m-i+1)!}\\ &=\dfrac{1}{m+1}\sum_{i=0}^{m}\binom{m+1}{i}B_in^{m-i+1} \end{align*}

Q.E.D