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

  • $\begingroup$ What is $P_r$, already? $\endgroup$ – Did Aug 28 '15 at 20:48
  • $\begingroup$ i meant sum of rth diagonal row , sorry bit confusing i will add image $\endgroup$ – Lethalbeast Aug 28 '15 at 20:50
  • 1
    $\begingroup$ Then the relation ${i\choose j}+{i\choose j+1}={i+1\choose j+1}$ is all one needs to prove this by induction. $\endgroup$ – Did Aug 28 '15 at 21:08

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 the formula $$\binom{n}{k}+\binom{n+1}{k}=\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?


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.


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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.