binomial theorem/ combinations question (1 Viewer)

[MzG1zi]

the question is :
simplify (n-1)^C k-1 <--subscript + (n-1)^C k <---subscript

(sorry for how weird it looks, i dont know how to do the subscript/superscripts thing on here)
i don't know how to solve it, so can someone please explain/show how?

 

[Trebla]

This is actually a Pascal's triangle relation. The sum of two adjacent coefficients at the nth row gives the coefficient on the (n + 1)th row hence



Proof:

 

[Pwnage101]

Trebla provides a nice algebraic proof of a well known result from Pascal's triangle. A non-algebraic (combinatorics) proof would go something similar to the following.

Assume n and k are positive integers, with n>k.

Consider Tom, who has (n-1) (distinct, distinguishable) blue marbles and 1 red marble (A total of n marbles).

-Scenario A. Consider the number of ways of choosing k marbles from the n, where the order they are chosen in is not important - this is simply nCk.

-Scenario B. Now, in the context of Scenario A, consider the 2 (mutually exclusive and exhaustive*) events: (1):{The red marble is one of the k chosen} and (2):{the red marble is NOT one of the k chosen}. With event:

(1): Since the red marble is chosen, Tom must select (k-1) blue marbles from the remaining (n-1) blue marbles; there are (n-1)C(k-1) ways of doing this.
(2): Since the red marble is NOT chosen, Tom must select k blue marbles from the (n-1) blue marbles available; there are (n-1)Ck ways of doing this.

Hence, since the two events were mutually exclusive, we can add the number of combinations from (1) and (2); since the events are exhaustive, this will give the exact number of combinations for Scenario B. Hence, the number of combinations in Scenario B are: [(n-1)C(k-1)+(n-1)Ck].

But, we know that Scenario A and Scenario B are identical to each other, hence: nCk=(n-1)C(k-1)+(n-1)Ck.

I wouldn't advise taking this route to answer exam questions, but it may be useful in strengthening your combinatoric skills.

*From Wikipedia:
- "In layman's terms, two events are mutually exclusive if they cannot occur at the same time (i.e., they have no common outcomes). An example is tossing a coin, which can result in either heads or tails, but not both. Both outcomes cannot happen simultaneously."

- "In probability theory, a set of events is jointly or collectively exhaustive if at least one of the events must occur. For example, when rolling a six-sided die, the outcomes 1, 2, 3, 4, 5, and 6 are collectively exhaustive, because they encompass the entire range of possible outcomes."