# Pascal's Rule

• Jul 6th 2010, 10:03 AM
minicooper58
Pascal's Rule
Hi this question was in Advanced Higher Maths in the UK
Show that (n+1 , 3) - (n ,3 )=(n ,2)
They are written in column vector form ie n+1 at top and 3 at the bottom for example for the first. I think you have to use the n c r formula to prove the rhs
it for this question using the identity:

(n , r-1)+(n ,r)=(n+1, r) written as column vectors

Thanks
• Jul 6th 2010, 10:10 AM
undefined
Quote:

Originally Posted by minicooper58
Hi this question was in Advanced Higher Maths in the UK
Show that (n+1 , 3) - (n ,3 )=(n ,2)
They are written in column vector form ie n+1 at top and 3 at the bottom for example for the first. I think you have to use the n c r formula to prove the rhs
it for this question using the identity:

(n , r-1)+(n ,r)=(n+1, r) written as column vectors

Thanks

I see you are unsatisfied by my responses in this thread. Why not just ask about what you didn't understand?
• Jul 6th 2010, 11:34 AM
Also sprach Zarathustra
Pascal's Rule
Combinatorial proof:

Pascal's Rule states:

\$\displaystyle {n\choose k} = {n-1\choose k} + {n-1 \choose k-1}\$

Proof:

Let \$\displaystyle x\$ be an element of group of \$\displaystyle n\$ elements.
The number of combinations of \$\displaystyle k\$ elements from group of \$\displaystyle n\$ elements, which is not containing the element \$\displaystyle x\$ is give by: \$\displaystyle {n-1\choose k}\$, now, the number of combinations which containing element \$\displaystyle x\$ is: \$\displaystyle {n-1 \choose k-1}\$.

But, every combination is containing \$\displaystyle x\$ or not containing \$\displaystyle x\$. Hence, the total number\$\displaystyle {n\choose k} \$ of combinations of \$\displaystyle k\$ from \$\displaystyle n\$ elements is the sum of the above.

Q.E.D