How to find this binomial summation

Question

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?

Answer 1

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.