It is well known that a recursive sequence or $1$-d sequence can be solved in $O log n$ time given that it has the form

$$a_n=sum_{k=1}^{n} C_ka_{n-k}$$

where $C_k$ is a constant. Examples would include polynomials like $n^2$ or $n^3$, exponentials like $2^n$, and Fibonacci Numbers defined by $a_n=a_{n-1}+a_{n-2}, a_0=0, a_1=1$. Factorials would not be included for example, because they are defined by $a_n=na_{n-1}$, and $C_k=n$ is not constant.

Let $a_{n,k}$ be a two dimensional sequence defined by

$$a_{n,k} = sum_{i=0,j=0, (ine n text{ }âˆ§text{ }jne k)}^{n,k}C_{i,j}a_{i,j}$$

where $C_{i,j}$ is constant.

Is it possible to compute $a_{n,k}$ in logarithmic time (a.k.a $O log n$) or better?

I know one case where this is possible, namely if $a_{n,k}$ are coefficients of polynomials in a sequence ($1$-d recursive sequence), such that the degrees of each term differ by $1$. In this case, the diagonals of the sequence $a_{n,n+t}$ for some constant $t$, are $1$-d constant recursive functions, whose terms can be computed in $Olog n$ time. This doesn’t use the initial relation in terms of two indices though as expected.

However, in certain cases, the diagonals do not form $1$-d constant recursive functions, namely when the degree difference of consecutive polynomial terms is more than $1$.