Question

Question: Let rand kbe integers such that$\mathbf{0}\mathbf{⩽}\mathit{r}\mathbf{⩽}\mathit{k}\mathbf{-}\mathbf{1}$. Prove that role="math" localid="1658916854694" $\mathbf{\left[}\begin{array}{c}\mathbf{K}\\ \mathbf{r}\mathbf{+}\mathbf{1}\end{array}\mathbf{\right]}\mathbf{+}\mathbf{\left[}\begin{array}{c}\mathbf{k}\\ \mathbf{r}\end{array}\mathbf{\right]}\mathbf{=}\mathbf{\left[}\begin{array}{c}\mathbf{K}\mathbf{+}\mathbf{1}\\ \mathbf{r}\mathbf{+}\mathbf{1}\end{array}\mathbf{\right]}$. [Hint: Use the fact that

role="math" localid="1658916890807" $\left(k-r\right)\left(k-\left(r+1\right)\right)\mathbf{!}\mathbf{=}\left(k-r\right)\mathbf{!}\mathbf{=}\left(\left(k+1\right)-\left(r+1\right)\right)\mathbf{!}$

to express each term on the left as a fraction with denominator$\left(k+1\right)\mathbf{!}\left(k-r\right)\mathbf{!}$ . Add the fractions, simplify the numerator, and compare the result with.$\left[\begin{array}{c}k+1\\ r+1\end{array}\right]$]

Short answer

Answer:

It is proved that $\left[\begin{array}{c}K\\ r+1\end{array}\right]+\left[\begin{array}{c}k\\ r\end{array}\right]=\left[\begin{array}{c}K+1\\ r+1\end{array}\right]$.

Step-by-step solution

Binomial Coefficient

For each r, with,0 < r < n the binomial coefficient $\left[\begin{array}{c}n\\ r\end{array}\right]$is defined to be the number$\frac{\mathbf{n}\mathbf{!}}{\mathbf{r}\mathbf{!}\left(n-r\right)\mathbf{!}}$$\frac{\mathbf{n}\mathbf{!}}{\mathbf{r}\mathbf{!}\left(n-r\right)\mathbf{!}}$.

Prove that [Kr+1]+[kr]=[K+1r+1].

Let r and k be integers.

Evaluate $\left[\begin{array}{c}K\\ r+1\end{array}\right]+\left[\begin{array}{c}k\\ r\end{array}\right]$as follows.

$$\begin{gathered} \left[\begin{array}{c}K\\ r+1\end{array}\right]+\left[\begin{array}{c}k\\ r\end{array}\right]=\frac{k!}{\left[k-\left(r+1\right)\right]!\left(r+1\right)!}+\frac{k!}{\left(k-1\right)!r!} \\ =k!\left[\frac{1}{\left[k-\left(r+1\right)\right]!\left(r+1\right)!}+\frac{1}{\left[\left(k+1\right)-\left(r+1\right)\right]!\left(r+1\right)!}\right] \\ =k!\left[\frac{r+1}{\left[\left(k+1\right)-\left(r+1\right)\right]!\left(r+1\right)!}+\frac{k-r}{\left[\left(k+1\right)-\left(r+1\right)\right]!\left(r+1\right)!}\right] \\ =k!\left[\frac{r+1+k-r}{\left[\left(k+1\right)-\left(r+1\right)\right]!\left(r+1\right)!}\right] \end{gathered}$$

Reduce the above solution.

$$\begin{gathered} \left[\begin{array}{c}K\\ r+1\end{array}\right]+\left[\begin{array}{c}k\\ r\end{array}\right]=k!\left[\frac{\left(k+1\right)!}{\left[\left(k+1\right)-\left(r+1\right)\right]!\left(r+1\right)!}\right] \\ =\left[\begin{array}{c}K+1\\ r+1\end{array}\right] \end{gathered}$$

Hence, it is proved that $\left[\begin{array}{c}K\\ r+1\end{array}\right]+\left[\begin{array}{c}K\\ r\end{array}\right]=\left[\begin{array}{c}K+1\\ r+1\end{array}\right]$.