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.
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.
$$\sum_{k=0}^n \binom{n}{k}\binom{n+1}{k}=\sum_{k=0}^n \binom{n}{k}\binom{n+1}{n+1-k}=\binom{2n+1}{n+1}$$
Combinatorial Solution:
There are $2n+1$ items, and you want to choose $n+1$ items in total.
$\binom{n}{k}$: First, you choose $k$ items from $n$
$\binom{n+1}{n+1-k}$: Next, you choose $n+1-k$ items from remaining $n+1$
$$ \sum_{k=0}^n\binom nk\binom{n+1}k=\sum_{k=0}^n\binom n{n-k}\binom{n+1}k=\binom{2n+1}n $$ For $\sum_{k=0}^n\binom n{n-k}\binom{n+1}k$ is the sum of $n$ cases of choosing $n$ balls from $2n+1$ balls.
Your sum is equal to $$I=\frac{1}{2\pi}\int_0^{2\pi}\left(\sum_{k=0}^{n}\binom{n}{k}e^{ikx}\right)\left(\sum_{l=0}^{n+1}\binom{n+1}{l}e^{-ilx}\right)dx$$ because $\int_0^{2\pi}e^{i(k-l)x}dx=2\pi$ iff $k=l$ and zero otherwise. Hence, $$I=\frac{1}{2\pi}\int_0^{2\pi}(e^{ix}+1)^n(e^{-ix}+1)^{n+1}dx=\frac{1}{2\pi}\int_0^{2\pi}e^{-i\frac{x}{2}}(e^{i\frac{x}{2}}+e^{-i\frac{x}{2}})^{2n+1}dx.$$ Since it is real we get $$I=\frac{2^{2n}}{\pi}\int_0^{2\pi}\cos^{2n+2}(\frac{x}{2})dx$$ Let $x=2u$, and since the integrant is even function, $$I=\frac{2^{2n+2}}{\pi}\int_0^{\frac{\pi}{2}}\cos^{2n+2}(u)du$$ By the help of https://en.wikipedia.org/wiki/List_of_integrals_of_trigonometric_functions $$I=\frac{2^{2n+2}}{\pi}\frac{(2n+1)(2n-1)(2n-3)...5.3.1}{(2n+2)(2n)(2n-2)......6.4.2}\frac{\pi}{2}$$ and $$I=2^{2n+1}\frac{(2n+1)(2n-1)(2n-3)...5.3.1}{(2n+2)(2n)(2n-2)......6.4.2}$$
