How to simpify the following equation involving binomial coefficients?
How can one simplify this equation:
$$ \sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1} $$
Algebraic argument:
$$(1+x)^n = \sum_{k=0}^{n} \dbinom{n}k x^k$$ $$(1+x)^n = \sum_{k=0}^{n} \dbinom{n}k x^{n-k}$$ Multiplying the above two we get that $$(1+x)^{2n} = \sum_{j=0}^n \sum_{k=0}^n \dbinom{n}j \dbinom{n}k x^{n-k+j}$$ Hence, the coefficient of $x^{n+1}$ in the product of the above two is (i.e. $j=k+1$) $$\sum_{k=0}^{n-1} \dbinom{n}{k+1} \dbinom{n}k$$ The coefficient of $x^{n+1}$ in $(1+x)^{2n}$ is $$\dbinom{2n}{n+1}$$ Hence, $$\sum_{k=0}^{n-1} \dbinom{n}{k+1} \dbinom{n}k = \dbinom{2n}{n+1}$$
Combinatorial argument:
Consider a bag with $n$ red balls and another bag with $n$ blue balls. Number of ways of choosing a total of $n+1$ balls is given by $$\dbinom{2n}{n+1}$$
Another way to count the same thing is if we select $k+1$ red balls from $n$ red balls, then we need to select $n-k$ blue balls from $n$ blue balls (equivalently we need to reject $k$ blue balls from $n$ blue balls). Hence, number of ways to do this is $\dbinom{n}{k+1} \dbinom{n}k$. To take all possible cases into account, we need to run $k$ from $0$ to $n-1$. Hence, we get the total number of ways is $$\sum_{k=0}^{n-1} \dbinom{n}k \dbinom{n}{k+1}$$