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."
