TITLE: How to find this binomial summation
QUESTION [2 upvotes]: 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?

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 2571189}