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 '15 at 14:13
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 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.