1
$\begingroup$

I was wondering how to prove that in general, if I take any row of Pascal's triangle and apply all of the coefficients of that row to adjacent entries of a later row, you'll get an entry in Pascal's triangle?

For instance, one can show that if you apply the coefficients $1,2,1$ in the second row to any later row, you get an entry in Pascal's triangle. More formally, $${n\choose r} + 2{n\choose r+1} +{n\choose r+2} = {n+2\choose r+2} \tag1$$ Similarly, showing that applying the coefficients of the third row to later rows results in an entry in Pascal's triangle would involve showing that $${n\choose r} + 3{n\choose r+1} + 3{n\choose r+2} + {n\choose r+3} = {n + 3\choose r+3} \tag2$$

I know how to show $(1)$ using the definition of choosing: ${n\choose k} = \frac{n^{\underline{k}}}{k!}$ and just expanding all terms and simplifying. But if one were to show the general case, perhaps some sort of induction would be required?

For instance, perhaps this is equivalent to showing that $$\sum_{i=0}^j {j\choose i} {n\choose r + i} = {n + j\choose r+j} \tag3$$ for $j\geq 1$. The base case is just Pascal's identity, and I know a combinatorial proof as well as an algebraic proof for it. Assume the inductive hypothesis. We need to show that $$\sum_{i=0}^{j+1} {j+1\choose i}{n\choose r+i}={n+j+1\choose r+j+1} \tag4$$ However, I can't find a good relationship b/w this step and the inductive hypothesis.

This is, in a way, a generalization of Pascal's Identity.

$\endgroup$
0
$\begingroup$

yes, it works. Here is how to do the induction, illustrated...

$${n\choose r} + 2{n\choose r+1} + {n\choose r+2} = $$ $$ \left\{ {n\choose r} + {n\choose r+1} \right\} + \left\{ {n\choose r+1} + {n\choose r+2} \right\} = $$

$$ $$ $$ $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$${n\choose r} + 3{n\choose r+1} + 3{n\choose r+2} + {n\choose r+3} = $$ $$ \left\{ {n\choose r} + 2{n\choose r+1} + {n\choose r+2}\right\} + \left\{ {n\choose r+1} + 2{n\choose r+2} + {n\choose r+3}\right\} = $$

$$ $$ $$ $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$${n\choose r} + 4{n\choose r+1} + 6{n\choose r+2} + 4{n\choose r+3} + {n\choose r+4}= $$ $$ \left\{ {n\choose r} + 3{n\choose r+1} + 3{n\choose r+2} +{n\choose r+3} \right\} + \left\{ {n\choose r+1} + 3{n\choose r+2} + 3{n\choose r+3} +{n\choose r+4} \right\} = $$

$\endgroup$

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.