• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q26E

Expert-verified
Found in: Page 422

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Let$$n$$and $$k$$ be integers with $$1 \le k \le n$$. Show that$$\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n + 2}\\{n + 1}\end{array}} \right)/2 - \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right)$$

The expression$$\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n + 2}\\{n + 1}\end{array}} \right)/2 - \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right)$$is proved.

See the step by step solution

## Step 1: Formula of Pascal identity

Pascal identity:

$$\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right) + \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)$$

## Step 2: Calculate the coefficient of $${x^{n + 1}}$$ in $${(1 + x)^{2n}}$$ in two ways

Coefficient of $${x^k}$$ in $${(1 + x)^n}$$ multiplied by coefficient of $${(1 + x)^{n - k + 1}}$$ in$${(1 + x)^n}$$over all possible values of $$k = \sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \cdot \left( {\begin{array}{*{20}{c}}n\\{n - k + 1}\end{array}} \right)$$.

Now, $$k = \sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \cdot \left( {\begin{array}{*{20}{l}}n\\{k - 1}\end{array}} \right)$$.

Coefficient of$${x^{n + 1}}$$in$${(1 + x)^{2n}}$$is $$\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right)$$.

## Step 3: Equate the coefficients and use the Pascal identity to prove the expression

Let $${\bf{n}}$$ be a positive integer.

$$\begin{array}{l}\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right)\\\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n + 1}\\{n + 1}\end{array}} \right)\end{array}$$

$$\begin{array}{l}\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 1)!}}{{(n + 1)!(2n + 1 - (n + 1))!}}\\\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 1)!}}{{(n + 1)!n!}}\end{array}$$

$$\begin{array}{l}\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 1)!}}{{(n + 1)!n!}} \cdot \frac{{2n + 2}}{{2n + 2}}\\\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 2)!}}{{(n + 1)!n!}} \cdot \frac{1}{{2n + 2}}\end{array}$$

$$\begin{array}{l}\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 2)!}}{{(n + 1)!n!}} \cdot \frac{1}{{2(n + 1)}}\\\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \frac{{(2n + 2)!}}{{(n + 1)!(n + 1)!}} \cdot \frac{1}{2}\end{array}$$

$$\left( {\begin{array}{*{20}{c}}{2n}\\{n + 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n + 2}\\{n + 1}\end{array}} \right)/2$$

Hence, $$\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{2n + 2}\\{n + 1}\end{array}} \right)/2 - \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right)$$.