# How is this a property of Pascal's triangle?

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.

-
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

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

-
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
@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

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.

-

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.

-

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

-