-1

I need to prove this general formula

$(1+x)^{n} = \sum_{k=0}^{n} \frac{n!}{k!(n-k)!}x^{k}$

And also prove to prove it on example - equivalence of $(1+x)^{5}$ and its expansion $1+5\frac{5}{1!}x+...+\frac{5!}{5!0!}x^{5}$ I would be very grateful for any help. Besides, I have some difficulty understanding correlation between $\frac{n!}{k!(n-k)!}x^{k}$ and $\sum_{k=0}^{n}\binom{n}{k}x^{n-k}$

Carsten S
  • 8,726
Dan
  • 127
  • I suspect you mean $(1+x)^n$. One can prove the general $(a+b)^n$ binomial theorem with mathematical induction. – John Jan 19 '14 at 09:17
  • For a proof by induction, See http://math.stackexchange.com/questions/502360/proof-of-abn1/502383#502383 – user91500 Jan 19 '14 at 09:22
  • @Dan To avoid downvotes and closure, you should show us more of your work. – John Jan 19 '14 at 09:26
  • Well, this task appeared when I was prooving equivalence of two definitions from Paskal's triangle (I've already done it)(Df.3 $(1+x)^{n} =: \sum_{k=0}^{n} \binom{n}{k}x^{k}$ and $Df.4 \binom{n}{k} := \frac{n!}{k!(n-k)!}$ If that's what you were looking for. I do understand that the question I've just asked is very general, anyway. – Dan Jan 19 '14 at 09:30
  • @Dan You should add you work to your question. Clarify, where your struggling. – John Jan 19 '14 at 09:35

2 Answers2

5

There are some proofs for the general case, that $$(a+b)^n=\sum_{k=0}^n {n \choose k}a^kb^{n-k}.$$ This is the binomial theorem.

One can prove it by induction on n:

  • base: for $n=0$, $(a+b)^0=1=\sum_{k=0}^0{n \choose k}a^kb^{n-k}={0\choose0}a^0b^0$.

  • step: assuming the theorem holds for $n$, proving for $n+1$: $$(a+b)^{n+1}=(a+b)(a+b)^n=(a+b)\sum_{k=0}^n {n \choose k}a^kb^{n-k}\\=\sum_{k=0}^n {n \choose k}a^{k+1}b^{n-k}+\sum_{k=0}^n{n \choose k}a^kb^{n-k+1}$$ Putting in the left summation $m=k+1$ gives:

$$\sum_{m=1}^{n+1} {n \choose {m-1}}a^{m}b^{n-m+1}+\sum_{k=0}^n{n \choose k}a^kb^{n-k+1}$$ Adding the two summation gives: $$b^{n+1}+\sum_{k=1}^n\left[{n \choose k}+{n\choose k-1}\right]a^kb^{n-k+1}+a^{n+1}$$ Now, it can be proved (in induction or combinatorial proof) that ${n \choose k}+{n\choose k-1}={n+1\choose k}$, reinsert the $a^{n+1}$ and $b^{n+1}$ into summation and the proof is complete.

Another way - combinatoric(less formal but simpler):

in the expression $(a+b)^n$, the coffecient of $a^kb^{n-k}$ is the number of ways to choose k 'a's and n-k 'b's from n pairs of $(a+b)$. For that we can choose k pairs for 'a's, and 'b's from the others. The number of ways to do it is ${n \choose k}$

Riddhiman
  • 33
LeeNeverGup
  • 2,671
  • Thanks a lot! I'll start adapting it to my case, that is $(1+x)^{n}$, right away. I may encounter some trouble with equivalence of factorial fraction(in my case) and binomial coefficient multiplication(in the very general case) to the right, though. – Dan Jan 19 '14 at 09:52
1

It should read: $(1 + x)^n$ = your RHS. You can use induction on $n$ and the formula: $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ to complete the induction step at $n + 1$.

Riddhiman
  • 33
DeepSea
  • 77,651