Question

Prove that \[^n{C_r} + {2^n}{C_{r - 1}}{ + ^n}{C_{r - 2}}{ = ^{n + 2}}{C_r}\]

Answer 1

Hint: We have to prove that the given combination expression is equal for this problem. We are going to prove this relation by solving the right hand side using some relations in combinations.
We know that: a combination is a mathematical technique that determines the number of possible arrangements in a collection of items where the order of the selection does not matter, in combinations, one can select the items in any order.
Now we apply a formula: \[^n{C_r}{ + ^n}{C_{r - 1}}{ = ^{n + 1}}{C_r}\]

Complete step-by-step answer:
We have to prove that, \[^n{C_r} + {2^n}{C_{r - 1}}{ + ^n}{C_{r - 2}}{ = ^{n + 2}}{C_r}\]
Let us take from right hand side,
\[{ \Rightarrow ^n}{C_r} + {2^n}{C_{r - 1}}{ + ^n}{C_{r - 2}}\]
Expanding the middle term, we get,
\[{ \Rightarrow ^n}{C_r}{ + ^n}{C_{r - 1}}{ + ^n}{C_{r - 1}}{ + ^n}{C_{r - 2}}\]
We know that,
\[^n{C_r}{ + ^n}{C_{r - 1}}{ = ^{n + 1}}{C_r}\]
Simplifying we get,
\[ \Rightarrow {(^n}{C_r}{ + ^n}{C_{r - 1}}) + {(^n}{C_{r - 1}}{ + ^n}{C_{r - 2}})\]
Applying the formula, we get,
\[{ \Rightarrow ^{n + 1}}{C_r}{ + ^{n + 1}}{C_{r - 1}}\]
Again, applying the formula, we get,
\[{ \Rightarrow ^{(n + 1) + 1}}{C_r}\]
Simplifying we get,
\[{ \Rightarrow ^{(n + 2)}}{C_r}\]

Hence, \[^n{C_r} + {2^n}{C_{r - 1}}{ + ^n}{C_{r - 2}}{ = ^{n + 2}}{C_r}\]

Note: A combination is a mathematical technique that determines the number of possible arrangements in a collection of items where the order of the selection does not matter, in combinations, one can select the items in any order.
Combinations can be confused with permutations. However, in permutations the order of the selected items is essential. For example, the arrangements \[ab\] and \[ba\] are equal in combination (considered as one arrangement), while in permutations, the arrangements are different.
To differentiate combination and permutation, let us consider an example.
Here is a statement that: “My fruit salad is a combination of apples, grapes and bananas" We don't care what order the fruits are in, they could also be "bananas, grapes and apples" or "grapes, apples and bananas", it’s the same fruit salad.
Here is another statement that: "The combination to the safe is 472". Now we do care about the order. "724" won't work, nor will "247". It has to be exactly 4-7-2.
First statement is an example of combination and the second statement is an example of permutation.