Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For all non-negative integers $k$ and $n$, $$ \dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \ldots + \dbinom{n}{k} = \dbinom{n +1}{k+1} $$

How is this a property of Pascal's triangle? I do not see at all how it relates. I'm looking for an explanation, as opposed to some calculation with algebraic manipulations.

share|improve this question
    
What are you asking? Are you wondering why it is true, or rather (as it would seem) why it has anything to do with Pascal's triangle? The latter seems obvious, as all binomial coefficients can be found in Pascal's triangle... –  Marc van Leeuwen Dec 26 '12 at 7:35
add comment

4 Answers

up vote 11 down vote accepted

The "usual" property of the Pascal triangle is $$\dbinom{n+1}{k+1} = \underbrace{\dbinom{n}{k+1}}_{\text{Up right term}} + \underbrace{\dbinom{n}k}_{\text{Up left term}}$$ Now proceed along the up right branch i.e. $$\dbinom{n}{k+1} = \underbrace{\dbinom{n-1}{k+1}}_{\text{Up right term}} + \underbrace{\dbinom{n-1}{k}}_{\text{Up right term}}$$ Now again take the up right branch and keep proceeding to finally end with $$\dbinom{k+1}{k+1} = \dbinom{k}{k}$$ Now put these together to get what you want.

EDIT

$\hskip2.5in$enter image description here \begin{align} \color{red}{\dbinom{n+1}{k+1}} & = \color{blue}{\dbinom{n}{k}} + \color{red}{\dbinom{n}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{red}{\dbinom{n-1}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \color{red}{\dbinom{n-2}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{red}{\dbinom{k+2}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{blue}{\dbinom{k+1}{k}} + \color{red}{\dbinom{k+1}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{blue}{\dbinom{k+1}{k}} + \color{blue}{\dbinom{k}{k}} \end{align}

share|improve this answer
    
Those are very helpful graphics, is there a particularly easy way to make things like that? (A program, etc?) –  AndrewG Dec 26 '12 at 1:22
4  
@AndrewGibson I made these pictures in $\LaTeX$ using TikZ. I am a big fan of TikZ :). If you are comfortable with $\LaTeX$, then TikZ is the thing to make the graphics. –  user17762 Dec 26 '12 at 1:26
    
Fantastic, thanks! –  AndrewG Dec 26 '12 at 1:28
    
wow [filler...] –  Belgi Dec 26 '12 at 21:07
add comment

To add to Marvis answer note that the first equality in his answer is correct by this combinatorical argument:

When chossing $k+1$ elements out of $n+1$ elements we have two choises (that do not intersect): Either the last (say we number them from $1$ to $n+1) $element is chosen or not.

In the case that the last element is not chosen we have to choose all $k+1$ elements from $n$ elements (since the last one isn't picked) and in the second case we only need to choose another $k$ elements.

share|improve this answer
add comment

You're asking, for example, for the sum of all the indicated cells of Pascal's triangle

$$ \begin{matrix} \cdot \\ \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \\ \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \end{matrix} $$

which is the same thing as the sum of the cells

$$ \begin{matrix} \cdot \\ \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \circ \\ \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \end{matrix} $$

because I've added in zero. Now, what do you know about the sum of adjacent cells of Pascal's triangle?

Of course, this method is still a calculation with algebraic manipulations, just organized in picture form.

share|improve this answer
add comment

By induction on $n$. If $n<k$ then the left hand side is an empty sum, and the right hand side has $0<n+1<k+1$ so $\binom{n+1}{k+1}=0$. For $n\geq k$ assume the result for $n-1$, so one has $$ \dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \ldots + \dbinom{n-1}{k} = \dbinom n{k+1}. $$ Substituting that into the equation to be proved, we need to show $\binom n{k+1}+\binom n{k\rlap{\phantom+}}=\binom{n+1}{k+1}$, which is a familiar identity.

There is also a direct combinatorial interpretation of the formula. If you choose a subset of $k+1$ from the $n+1$ numbers $\{0,1,\ldots,n\}$, the last selected number $i$ satisfies $k\leq i\leq n$, and the remaining $k$ numbers can be chosen in $\tbinom ik$ ways among $\{0,\ldots,i-1\}$. Every subset is accounted for exactly once, so $$\sum_{i=k}^n\binom ik=\binom{k+1}{n+1}. $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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