0

I have two series, say $\{a_k\}$ and $\{b_k\}$ for $k=0, 1, \ldots$. They are related to each other as

$$\sum_{r=0}^k \binom{k}{r} b_r = a_k.$$

I want to compute $b_k$'s. Of course, I can do this using the following recurrence relation

$$b_k = a_k-\sum_{r=0}^{k-1}\binom{k}{r} b_r.$$

But this is quite time consuming as $k$ increases because the number of operations is $O(k)$. Is there a possibility that we can have a recurrence relation to obtain $b_k$ in $O(1)$ time?

Raymond Kan
  • 1
  • 3
  • Also: https://math.stackexchange.com/q/1155541/42969. – Martin R Jul 22 '19 at 19:49
  • This is not what I need, the explicit relation is still $O(k)$, and I want something that is $O(1)$. – Raymond Kan Jul 22 '19 at 19:52
  • 1
    Your formula for $b_k$ is a function that depends at least implicitly on each of $a_0,\ldots,a_k$, so it would seem you need $\Omega(k)$ operations to compute it. – J.G Jul 22 '19 at 20:06
  • If $a_k$ is known, then a specific formula may be derived. – Varun Vejalla Jul 22 '19 at 21:40
  • $a_k$ is indeed known and precomputed. I just want to compute $b_k$ recursively in $O(1)$ time, possibly using $a_{k}$, $a_{k-1}$, and $b_{k-1}$ (or more terms but not all the way to $a_0$ and $b_0$). – Raymond Kan Jul 22 '19 at 21:57

0 Answers0