2
$\begingroup$

How to calculate this?$$\sum_{x = 0}^n \sum_{y = 0}^n a^x b^y\binom{x + y}{y}$$

I tried the following approach by replacing $x + y = t$ and then solving $\sum_{t\ =\ 0}^{2n}\sum_{r=max(0,\ t - n)}^{min(n,\ t)} a^r b^{t - r}\binom{t}{r}$ but this got me nowhere. Maybe we can reduce it to one summation instead of two which can be solved in $\mathcal{O(n)}$ time then?

$\endgroup$
1
$\begingroup$

We can generate a recurrence like this.

Let's denote $S(t) = \sum_{r\ =\ max(0, t - n)}^{min(n, t)}a^rb^{t - r}\binom{t}{r}$. Now $\forall 1 \leq t \leq n,\ S(t) = (a+b)S(t - 1)$

So, for calculating $S(t),\ \forall t > n$ notice \begin{align*} S(n + 1) = (a+b)^{n+1} - \binom{n + 1}{0}a^{n + 1} - \binom{n + 1}{0}b^{n + 1}\\ S(n + 1) = (a + b)S(n) - \binom{n + 1}{0}a^{n + 1} - \binom{n + 1}{0}b^{n + 1} \end{align*} Now, using the identity $$\binom{n}{r} = \binom{n-1}{r - 1} + \binom{n}{r - 1}$$. We can write $S(n + 2)$ as \begin{align*} S(n + 2) = (a + b) * S(n + 1) - \binom{n + 2}{1}a^{n+1}b^1 - \binom{n + 2}{1}a^1b^{n + 1} \end{align*} Similarly, we can calculate $$S(i) = (a+b)S(i-1) - \binom{i}{i - n - 1}a^{n + 1}b^{i - n - 1} - \binom{i}{i - n - 1}b^{n + 1}a^{i -n - 1}$$ Hence, each time we are decreasing two appropriate terms after multiplying it $(a + b)$. This all works because of the identity stated above. Hence, you can calculate it all $S(i)$ in $\mathcal{O(n)}$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.