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?

Oscillatory

I would suggest to upload your figure image to SO. – Rickyrico

Click on the picture icon while editing (on the top, right from {}). If the image appears to big for you, see also here – Rickyrico

Looks as if it takes significant mathematical effort to find and prove faster methods of computation: en.wikipedia.org/wiki/… – Parasiticide

Hmm...so you mean to say that there's no more efficient way of solving this without applying the kind of mathematics that they have applied? – Oscillatory

@NikharAgrawal: I mean to say that if there was an easy way of doing it as efficiently as those papers do it, then finding a harder way to do it that efficiently would not have been worth publishing :-) – Parasiticide

hmm...True enough I guess. :) – Oscillatory

Assuming you're using a 1-based index. – Whoso

Voting to close as off-topic - theoretical cs or math (as the tags would suggest) – Clegg

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.

Sweeper