<s>[INST] Evaluating $\binom{n}{0}\binom{n+1}{0}+\binom{n}{1}\binom{n+1}{1}+\ldots+\binom{n}{n-1}\binom{n+1}{n-1}+\binom{n}{n}\binom{n+1}{n}$ Here's a question that arose when I was trying to solve a probability problem in my textbook. I'm trying to calculate the sum:
$$\binom{n}{0}\binom{n + 1}{0} + \binom{n}{1}\binom{n + 1}{1} + \binom{n}{2}\binom{n + 1}{2} + \ldots + \binom{n}{n - 1}\binom{n + 1}{n - 1} + \binom{n}{n}\binom{n + 1}{n}$$
But I'm not sure how to get started with evaluating this. Could anyone help? Any hints would be well-appreciated.
 [/INST] Let's use the binomial theorem to find:
$$(1 + x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n$$
and
$$(x + 1)^{n + 1} = \binom{n + 1}{0}x^{n + 1} + \binom{n + 1}{1}x^n + \binom{n + 1}{2}x^{n - 1} + \cdots + \binom{n + 1}{n}x + \binom{n + 1}{n + 1}$$
Let's look at the coefficent of the term $x^{n + 1}$ in the product of these two.
$x^{n + 1}$ can be formed by multiplying $\binom{n}{0}x^0$ with $\binom{n + 1}{0}x^{n + 1}$, $\binom{n}{1}x^1$ with $\binom{n+1}{1}x^{n}$ a.s.o.
In other words the coefficient of $x^{n + 1}$ in $(x + 1)^{n + (n + 1)}$ is what you're looking for.
So, answer $${\binom{2n + 1}{n + 1}}$$
PS. This is a very frequently used technique to solve such type of problems.
</s>