3
$\begingroup$

Prove that the binomial identity ${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$ is true using the following expression: $(1+x)^n = (1+x)(1+x)^{n−1}$ and the binomial theorem.

What I have:

We know from the binomial theorem that:

$$(x+1)^n= {n\choose 0} x^0 + {n\choose 1} x^1+\cdots+{n\choose k} x^k+\cdots+ {n\choose n-1} x^{n-1}+ {n\choose n} x^n.$$

By using the property that $(1+x)^{n} = (1+x)(1+x)^{n−1}$, we can take out a factor of $x$ to get:

$$x(x+1)^{n-1}={n-1\choose 0} x^0+\cdots+{n-1\choose k-1} x^{k-1}+\cdots+{n+1\choose n-1} x^{n-1}$$

If we then divide by a factor of $x$ we get:

$$1(x+1)^{n-1}={n-1\choose 0} x^0+\cdots +{n-1\choose k-1} x^k+\cdots+{n-1\choose n-1} x^{n-1}$$

Substituting $(x+1)^{n-1}={n-1\choose 0} x^0 +\cdots+{n-1\choose k-1} x^k+\cdots+{n-1\choose n-1} x^{n-1}$ into the equation $x(x+1)^{n-1}= {n-1\choose 0} x^0+\cdots+{n-1\choose k-1} x^{k-1}+\cdots+ {n+1\choose n-1}x^{n-1}$, the equation can be reduced to:

$${n\choose k}x^k = {n-1\choose k-1} x^{k-1}x+{n-1 \choose k}x^k 1$$

Dividing by $x$ we get: ${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$

Is this a good proof? What can I do to improve it? Is there a better way to solve this problem?

$\endgroup$
1
  • 2
    $\begingroup$ For math formatting, I think \binom{n}{k} works better than n \choose k. If you have to insert $ in the middle of an equation then you're not using good typesetting in the first place. Perhaps it would help to review meta.math.stackexchange.com/q/5020/139123 $\endgroup$
    – David K
    Apr 23, 2015 at 14:13

3 Answers 3

2
$\begingroup$

First of all, in general

$$x(x+1)^{n-1} \neq \binom{n-1}{0} x^0+\cdots+\binom{n-1}{k - 1}x^{k-1}+\cdots + \binom{n+1}{n-1}x^{n-1}.$$

Notice that as $x\to 0$ the left side goes to zero but the right side does not. Also, in general

$$1(x+1)^{n-1} \neq \binom{n-1}{0}x^0+\cdots+\binom{n-1}{k - 1}x^{k}+\cdots+ \binom{n-1}{n - 1}x^{n-1}.$$

If you change $x^k$ to $x^{k-1}$ on the right hand side, the two sides are equal. The step where you "reduce" an equation to $\binom nk x^{k} = \binom{n-1}{k - 1} x^{k-1}x + \binom{n-1}{k}x^{k}1$ has no clear explanation, but it doesn't really matter since the premises of that statement are already false.

$\endgroup$
1
$\begingroup$

A much shorter way would be calculating the coefficient of $x^k$ independently from each side of $$(1+x)^n=(1+x)(1+x)^{n-1}$$

Using the binomial theorem, the coefficient of $x^k$ on the LHS is $\binom{n}{k}$.

For the right hand side, $x^k$ can be formed by two ways -

  1. Selecting $1$ from $(1+x)$ and $x^k$ from $(1+x)^{n-1}$. This gives coefficient $\binom{n-1}{k}$.
  2. Selecting $x$ from $(1+x)$ and $x^{k-1}$ from $(1+x)^{n-1}$. This gives coefficient $\binom{n-1}{k-1}$.

So the total coefficient of $x^k$ on the RHS is $\binom{n-1}{k} + \binom{n-1}{k-1}$.

Since LHS=RHS, $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$

$\endgroup$
1
  • $\begingroup$ Sorry, no. Can you explain a little further? $\endgroup$
    – EmaLee
    Apr 23, 2015 at 14:19
1
$\begingroup$

Your proof can be slightly modified as follows:

Note that

$x(x+1)^{n-1}=x^n+{n-1 \choose 1}x^{n-1}+{n-1 \choose 2}x^{n-2}+...+{n-1 \choose n-2}x^2+x$

$(x+1)^{n-1}=x^{n-1}+{n-1 \choose 1}x^{n-2}+{n-1 \choose 2}x^{n-3}+...+{n-1 \choose n-2}x+1$

Add the 2 equations and look at the addition of like terms.

$(x+1)^n=x^n + ({n-1 \choose 1}+{n-1 \choose 0})x^{n-1} + ({n-1 \choose 2}+{n-1 \choose 1})x^{n-2}+...+({n-1 \choose n-1}+{n-1 \choose n-2})x+1$

Expand $(x+1)^n$ and see how the identity can be proved.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .