Calculating the Bernoulli numbers

In this post, I would like to demonstrate how to calculate the Bernoulli numbers. The Bernoulli numbers are a sequence of rational numbers and they’re usually denoted B_n. If you want a list of their values, you can go to the OEIS … oh, wait, you can’t actually look them up directly in the OEIS because they are not integers. But, hey, since they are rational numbers, you can just look up their numerators and denominators separately 😆.

The reason why I am interested in them is that they can be used to evaluate the Riemann Zeta function, as is explained in this paper. This great mathologer video gives another reason why one might be interested in the Bernoulli numbers and also explains how Bernoulli found them in the first place. This will help you understand this post’s featured image. Eventually, the mathologer video leads up to the Euler-Maclaurin formula, which is also the underlying reason why the Bernoulli numbers are useful for evaluating the Riemann Zeta function.

In the following we will aside the genesis and applications of the Bernoulli numbers and we will not discuss the convergence of the series through which we define them. We will assume that this has been taken care of. This post is about the numerical calculation of the Bernoulli numbers.

1. The arithmetic

The Bernoulli numbers are defined via the power series of the following fraction:
\frac{z}{e^z-1} = \sum_{n=0}^{\infty} \frac{B_n}{n!}z^n

To get a handle on the Bernoulli numbers, which are the parts of the coefficients denoted by B_n, it helps to observe the following expansion of the inverse fraction first:
\frac{e^z - 1}{z} = \frac{1}{z} \left(-1 + \sum_{k=0}^{\infty} \frac{z^k}{k!} \right) = 1 + \frac{z}{2!} + \frac{z^2}{3!} + \ldots = \sum_{k=0}^{\infty}\frac{z^k}{(k+1)!}
Here we have only used the well-known series expansion of the exponential function and then multiplied out the 1/z factor and re-written the result as a sum.

No, if we multiply both fractions, we get the following relation:
\frac{e^z-1}{z} \frac{z}{e^z-1} = 1 = \left(\sum_{n=0}^{\infty}\frac{B_n}{n!}z^n\right) \left(\sum_{k=0}^{\infty}\frac{z^k}{(k+1)!}\right)
and we just imagine that this product has its own power series expansion \sum_{m} c_m z^m. We know that this series has to be equal to 1 regardless of the value of z. And it is not hard to find out that they obey the following relation:
c_m = \sum_{k=0}^{m} \frac{1}{k! (m-k+1)!} B_k = \frac{1}{(m+1)!} \sum_{k=0}^{m} {m+1 \choose k} B_k (1)

To obtain this expression of the c_m we have used what is commonly known as the Cauchy product formula. But this just means that if we have to sums \sum_k a_k z^k and \sum_m b_m z^m and their prodcut expansion \sum_n c_n z^n then we just “collect” all terms from the original two series where k+m = n. For example:
(a_0 + a_1 z) (b_0 + b_1 z) = (a_0 b_0 + a_0 b_1 z + a_1 b_0 z + a_1 b_1 z^2)
Here, we have two possible combinations of a-b-factors in front of the linear term(s). Therefore, the coefficient in the prodcut’s expansion needs to sum over those. And in the infinite case we can ignore the fact that our toy example has a larger highes term in z.

Ok, back to our main result:
c_m = \sum_{k=0}^{m} \frac{1}{k! (m-k+1)!} B_k = \frac{1}{(m+1)!} \sum_{k=0}^{m} {m+1 \choose k} B_k (1)
Here, we can easily check (if we remember that {m+1 \choose k} = \frac{(m+1)!}{(m-k+1)!k!}) that c_0 = B_0 = 1. Since the total product is identically equal to 1 and c_0 is already equal to 1, we know that c_m = 0 \text{ for } m\geq 1.

2. The triangle

Ok, so far we have managed to get the first Bernoulli number B_0 = 1. But given the fact that all c_m must be zero, we can write down the equations for the next few Bernoulli numbers. Let’s do this and then discuss how to solve that:

m=1: B_0 + {2\choose 1} B_1 = B_0 + 2 B_1 = 0
m=2: B_0 + {3\choose 1} B_1 + {3\choose 2} B_2 = B_0 + 3 B_1 + 3 B_2 = 0
m=3: B_0 + {4\choose 1} B_1 + {4 \choose 2} B_2 + {4\choose 3} B_3 = B_0 + 4 B_1 + 6 B_2 + 4 B_3 = 0

Now, if we stare at this for a while, we might actually realize that the coefficients of the B_n in this list of equations are actually the entries in Pascal’s triangle. That is, we are laying out all binomial coefficients where the “numerator” of the binomial coefficient increases row-wise and the “denominator” increases within a row.

Therefore, the coefficients of the B_n in any given row are obtained by summing the “neighbouring” coefficients of the previous row, just as one would do it in Pascal’s triangle. The first few Bernoulli numbers are thus:

Thre first few Bernoulli numbers

Note that the Bernoulli numbers with odd index greater than 1 are all zero, not just those first two of this kind that can be seen in this table. Wikipedia has a section on why this is the case.

3. The code

For my personal usage I have compiled a small Python function that returns the k-th Bernoulli number. I have not optimized this in any way, for example, I have not added an early exit condition for odd k. I have also not added any caching here, so all numbers will always be calculated from the tip of the triangle.

def my_bernoulli(k):
coefficients = [1]
B = [1]
for i in range(1, k+1):
new_coefficients = coefficients
coefficients = coefficients + [1]
new_coefficients = new_coefficients + [1]
for j in range(1, i+1):
new_coefficients[j] = coefficients[j-1] + coefficients[j]
sum = -B[0]
for j in range(1, i):
sum -= new_coefficients[j] * B[j]
coefficients = new_coefficients

return B[k]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s