I am studying Pascal's identity but I can't understand how the last step of the equation below is derived.

Note: The identity which is being used here is $\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$ and in particular this is applied for the first terms in the left of every row.

\begin{array} \ \dbinom{n}{k} &=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} \\ &=\dbinom{n-2}{k} +\dbinom{n-2}{k-1}+\dbinom{n-1}{k-1} \\ & = \dbinom{n-3}{k}+\dbinom{n-3}{k-1} +\dbinom{n-2}{k-1} +\dbinom{n-1}{k-1} \\ \end{array}

In the end we have :

$\dbinom{n}{k}=\dbinom{k-1}{k-1}+\dbinom{k}{k-1}+\dbinom{k+1}{k-1} +\cdots + \dbinom{n-1}{k-1}$

This last step really confuses me,I can't make sense of it.

By looking at the identity we have used for every beginning term , I would think that the first two binomal coefficients of the last step should have a form like $\dbinom{r-1}{k} +\dbinom{r-1}{k-1}$ ,but I don't have this form so the author must have used something else also...

Can someone help me understand why the last step look so ?


You could write that first term as $\dbinom{k}{k}$, but note that $\dbinom{k}{k} = 1 = \dbinom{k-1}{k-1}$ so the adjustment is made as a nicety to make the lower expression more consistent across the formula.

  • 1
    $\begingroup$ Thanks for your response.(Couldn't the author point this at least or is this too trivial lol ?) $\endgroup$ – Mr. Y Jan 16 '16 at 20:58
  • $\begingroup$ @Mr.Y: I didn't find this initially obvious either, but some others might. $\endgroup$ – Daniel R. Collins Jan 17 '16 at 18:23

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.