Cómo hallar esta suma binómica

Question

¿Cómo calcularlo? $$\sum_{x = 0}^n \sum_{y = 0}^n a^x b^y\binom{x + y}{y}$$

He probado el siguiente método sustituyendo $x + y = t$ y luego resolver $\sum_{t\ =\ 0}^{2n}\sum_{r=max(0,\ t - n)}^{min(n,\ t)} a^r b^{t - r}\binom{t}{r}$ pero esto no me llevó a ninguna parte. Tal vez podamos reducirlo a una suma en lugar de dos que se puede resolver en $\mathcal{O(n)}$ ¿tiempo entonces?

Answer 1

Podemos generar una recurrencia como ésta.

Denotemos $S(t) = \sum_{r\ =\ max(0, t - n)}^{min(n, t)}a^rb^{t - r}\binom{t}{r}$ . Ahora $\forall 1 \leq t \leq n,\ S(t) = (a+b)S(t - 1)$

Así, para calcular $S(t),\ \forall t > n$ aviso \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*} Ahora, utilizando la identidad $$\binom{n}{r} = \binom{n-1}{r - 1} + \binom{n}{r - 1}$$ . Podemos escribir $S(n + 2)$ como \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*} Del mismo modo, podemos calcular $$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}$$ Por lo tanto, cada vez que estamos disminuyendo dos términos apropiados después de multiplicarlo $(a + b)$ . Todo esto funciona gracias a la identidad indicada anteriormente. Por lo tanto, se puede calcular todo $S(i)$ en $\mathcal{O(n)}$ tiempo.