2

I was working on a programming problem wherein I had to display pascal's triangle, so I went into binomial coefficients, and find out above formula $\;\displaystyle\binom n{k+1}=\binom n k\cdot\frac{n-k}{k+1}\;$ to fetch the next pascal's number in a row, knowing $1$ will be the first item in the row, I can use it to produce next pascal number in a row.

I tried googling around trying to find the proof but all in vain. Can someone redirect to some links or help me with the solution for this. Thanks in advance.

Angelo
  • 12,328
Aamir
  • 123

3 Answers3

5

Here is a bijective proof that $(k+1)\binom n{k+1} = (n-k)\binom n k$. Given $n$ items, we count the number of ways of choosing $k+1$ items, with one marked item. First, we can select $k+1$ items and then mark one of the items in $k+1$ ways. This gives the left hand side. On the other hand, we can choose $k$ items, and then pick one of the remaining $n-k$ items and mark it. This gives the right hand side.

Anand
  • 1,226
3

There are two ways to do any combinatorial related proof.

  1. Algebraic: $$\binom nr=\frac{n!}{r!(n-r)!}$$

Here we see: $$\binom{n}{k+1}=\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!}{k!(k+1)(n-k)!(\frac{1}{n-k})}=\binom nk\cdot\frac{n-k}{k+1}$$

  1. Combinatoric:

Anand's answer does this excellently

Rhys Hughes
  • 12,842
  • your answer is great, however I have one small doubt...u mind joining me in a chat room if possible? – Aamir May 24 '21 at 19:58
  • Of course, or you can just write your doubts here in the comments. – Rhys Hughes May 24 '21 at 22:37
  • How this step (k+1)!(n−k−1)! in denominator transformed to k!(k+1)(n−k)!(1n−k) I went through falling factorial concept to understand this transformation, but still I am in doubt about it. Please explain this. – Aamir May 25 '21 at 07:53
  • $$(k+1)!=(k+1)\cdot k \cdot (k-1)\cdot... \cdot 1=(k+1)k!$$ For example $4!=4\cdot 3\cdot 2 \cdot 1=4(3\cdot 2 \cdot 1)= 4\cdot 3!$. For the other part, I simply divided that through by $(k+1)$, so $j!=\frac{(j+1)!}{j+1}$ where $j=n-k-1$. In the numerical example, that is $3!=\frac{4!}{4}$ – Rhys Hughes May 25 '21 at 13:57
  • 1
    I got it now, thanks for explaining @Rhys Hughes. – Aamir May 25 '21 at 18:49
1

Your formula is correct.

$\displaystyle\binom n{k+1}=\binom n k\cdot\frac{n-k}{k+1}\;.$

Proof :

$\displaystyle\begin{align}\binom n{k+1}&=\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!\cdot(n-k)}{k!(n-k)!\cdot(k+1)}=\\&=\binom n k\cdot\frac{n-k}{k+1}\;.\end{align}$

Angelo
  • 12,328