today i was reading about pascal's triangle. the website pointed out that the 3th diagonal row were the triangular numbers. which can be easily expressed by the following formula.
$$\sum_{i=0}^n i = \frac{n(n+1)}{2}$$
i wondered if the following rows could be expressed with such a simple formula.
when trying to find the sum for the 3th row i used a method called "differences" i found on this site: http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalSquares.htm
lets call $P_r$ the $r^{th}$ row of pascals triangle. The result for the 4th row was
$$\sum_{i=0}^n P_3 = \frac{n(n+1)(n+2)}{6}$$
and the result for 4th row was
$$\sum_{i=0}^n P_4 = \frac{n(n+1)(n+2)(n+3)}{24}$$
i guessed the sum of the 5th row would be
$$\sum_{i=0}^n P_5 = \frac{n(n+1)(n+2)(n+3)(n+4)}{120}$$
i plotted the function and looking at the graph it seems to be correct.
it looks like the the sum of each row is:
$$\sum_{i=0}^n P_r = \frac{(n + 0)\cdots(n+(r-1))}{r!}$$
is this true for all rows? and why?
i think this has something to do with combinatorics/probability which i never studied.
thanks in advance
edit image for $P_r$: http://i.imgur.com/JlVC4q3.png
Best Answer
So you basically want to prove that $$\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\dotsc+\binom{n+k}{n}=\binom{n+k+1}{n+1}$$ holds for all $n,k$, right? Of course you can prove this using induction and Pascal's formula $$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$$ as suggest by Did. There is a nice combinatorial interpretation of this using double-counting: Suppose you have $n+1$ eggs, $n$ of them blue and 1 red.
You want to choose $k+1$ of them which is the RHS: $\binom{n+1}{k+1}$
Either you choose the red one in which case you have $\binom{n}{k}$ possibilities for the remaining ones.
Either you don't choose the red one in which case you have $\binom{n}{k+1}$ possibilities for the remaining ones.
Can you think of a similar combinatorial argument which directly works for the original sum?
Hint: Think of $n+k+1$ balls in a row labelled $1,2,\dotsc,n+k+1$. You want to choose $n+1$ of them. That's the RHS: $\binom{n+k+1}{n+1}$. Now, distinguish cases about which is the rightmost ball you choose. If it's the ball number $n+k+1$ you have $\binom{n+k}{n}$ possibilities to choose the remaining $n$ balls. If it's the ball number $n+k$ you have $\binom{n+k-1}{n}$ possibilities etc. Can you complete it from here?