What is the most efficient way of finding the first element of the ith row when A[i,j]=j*(A[i-1,j+1]-A[i-1,j])?

Question

When the first row is 1, 1/2 , 1/3 .... Here's an image to support the question.

Does there exist a more efficient approach than the naive O(n^2) approach?

I came across this when studying Bernoulli numbers and then consequently on reaching "Akiyama–Tanigawa algorithm".

One of the ways could be simple precomputing the results and storing them in a table. Since Bernoulli numbers grow very quickly, for most practical purposes we wouldn't need Bernoulli numbers for much larger n. Consider Bernoulli(400)- its around -(10^550).

But looking at it only algorithmically, is there a better approach than the O(n^2) one?

Answer 1

The first elements form the sequence of Bernoulli numbers. The numerators and denominators for the Bernoulli numbers are found using the A027641 sequence and A027642 sequence, respectively. Both of those sequences have closed-form sums on their respective pages that can be used to compute their terms.