If sequences $\{a_k\}$ and $\{b_k\}$ are related by $a_k = \sum_{r=0}^k \binom{k}{r} b_r$, can I compute $b_k$s in $O(1)$ time?

45 Views Asked by At

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?