1

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$: https://i.stack.imgur.com/3BdRn.png

Lethalbeast
  • 11

3 Answers3

7

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?

Community
  • 1
Tintarn
  • 2,931
1

Just to be more explicit, here is a proof of: $$\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+...+\binom{n+k}{n}=\binom{n+k+1}{n+1}$$I will use the property suggested by Did which is valid for general $i$ and $j$, \begin{equation}\binom{i}{j}+\binom{i}{j+1}=\binom{i+1}{j+1}\end{equation}

Proof: \begin{align} \binom{n+k+1}{n+1} & =\binom{n+k}{n}+\binom{n+k}{n+1}\qquad\text{Using above property}\\ &=\binom{n+k}{n}+\left\{\binom{n+k-1}{n}+\binom{n+k-1}{n+1}\right\}\\ &=\binom{n+k}{n}+\binom{n+k-1}{n}+\left\{\binom{n+k-2}{n}+\binom{n+k-2}{n+1}\right\}\\ &=\binom{n+k}{n}+\binom{n+k-1}{n}+\binom{n+k-2}{n}+...+\left\{\binom{n+1}{n}+\binom{n+1}{n+1}\right\}\\ &=\binom{n+k}{n}+\binom{n+k-1}{n}+\binom{n+k-2}{n}+...\binom{n+1}{n}+\binom{n}{n} \end{align} Hence proved.

Rohan Pote
  • 11
  • 3
0

Try performing the following multiplication, then look up the Binomial Theorem.

$$\begin{array}{lr} &\binom{5}{5}x^5+\binom{5}{4}x^4+\binom{5}{3}x^3+\binom{5}{2}x^2+\binom{5}{1}x+\binom{5}{0}\\ \times&x+1\\ \hline \end{array}$$

John Joy
  • 7,790