Combinatorial Proof: $ n\binom {n-1}{k-1} = k \binom nk$ , where $n$ is a positive integer and $k$ is an integer.

Question

I have trouble coming up with combinatorial proofs. How would you justify this equality?

$$ n\binom {n-1}{k-1} = k \binom nk $$ where $n$ is a positive integer and $k$ is an integer.

Answer 1

Say we want to choose a baseball team of $k$ players from $n$ players and we want to choose a captain for the baseball team. We can count the above in two different ways.

$1$. Choose the captain first. This can be done in $n$ ways. Now choose the rest of the team, i.e., we need to choose $k-1$ people from the remaining $n-1$ people, which can be done in $\dbinom{n-1}{k-1}$ ways.

$2$. Choose the team first, i.e., choose $k$ players from $n$ players. This can be done in $\dbinom{n}k$ ways. Now once we have these $k$ players, the captain can be chosen in $k$ ways.

Answer 2

I would write the expression for the binomial coefficients in terms of factorials and notice what happens.

Answer 3

We have a group of $n$ people, and want to count the number of ways to choose a committee of $k$ people with Chair.

For the left-hand side, we select the Chair first, and then $k-1$ from the remaining $n-1$ to join her.

For the right-hand side, we choose $k$ people, and select one of them to be Chair.

Answer 4

Since k is on the right-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . , switch the sides so it is on the left-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . .

Multiply multiply To compute a product; to perform a multiplication. n by each term term Any expression written as a product or quotient. Example: 2xy , , or inside the parentheses parentheses Marks of inclusion (symbols: ( and ) ). Parentheses is the plural form of parenthesis. .

Multiply multiply To compute a product; to perform a multiplication. k by each term term Any expression written as a product or quotient. Example: 2xy , , or inside the parentheses parentheses Marks of inclusion (symbols: ( and ) ). Parentheses is the plural form of parenthesis. .

Since k is on the right-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . , switch the sides so it is on the left-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . .

Since the variable variable A letter used to represent a number value in an expression or an equation. is in the denominator denominator The bottom part of a fraction. on the left-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . , this can be solved as a ratio ratio A pair of numbers that compares different types of units. . For example, is equivalent equivalent Two or more expressions that have the same value. to

Since k is on the right-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . , switch the sides so it is on the left-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . .

Reduce the expression expression A mathematical symbol, or combination of symbols, representing a value, or relation. Example: 2+2=4 by canceling out all common factors factor One of two or more expressions that are multiplied together to get a product. from the numerator numerator The top part of a fraction. and denominator denominator The bottom part of a fraction. .

k-1=(n-1)

Remove the parentheses parentheses Marks of inclusion (symbols: ( and ) ). Parentheses is the plural form of parenthesis. around the expression expression A mathematical symbol, or combination of symbols, representing a value, or relation. Example: 2+2=4 n-1.

k-1=n-1

Since -1 does not contain the variable variable A letter used to represent a number value in an expression or an equation. to solve for, move it to the right-hand side of the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . by adding 1 to both sides.

k=1+n-1

Subtract 1 from 1 to get 0.

k=n

To rewrite as a function function A set of ordered pairs where each first element is paired with one and only one second element and no element in either pair is without a partner. of n (e.g. f(n)), write the equation equation A mathematical statement that says two expressions have the same value; any number sentence with an = . so that k is by itself on one side of the equal sign and an expression expression A mathematical symbol, or combination of symbols, representing a value, or relation. Example: 2+2=4 involving only n is on the other side.

f(n)=n