Laws of binomial theorem

Hello folks , i wanted to discuss some really cool derivations and formulas related to binomial theorem . There is so much material on this topic that i will have to do a part 2 next week. For now , we will be focusing on proving one formula.

The Total number of terms in expansion of

(a1+a2+a3++ak2+ak1+ak)n \large (a_1+a_2+a_3+\cdots+a_{k-2}+a_{k-1}+a_k)^{n}

is equal to (n+k1n) \dbinom{n+k-1}{n} or (n+k1k1) \dbinom{n+k-1}{k-1}

where n n represents the power of the expression

and k \quad k represents the numbers of terms .

Now sit back tight and get some popcorn . Let's begin with the proof !

proof: From Multinomial theorem the general term of the expansion can be written as

n!n1!n2!nk1!nk!×a1n1a2n2ak1nk1aknk \large \displaystyle \sum \dfrac{n!}{n_1 ! n_2 ! \cdots n_{k-1}! n_{k}! } \times a_{1} ^{n_1}\cdot a_{2} ^{n_2}\cdots a_{k-1} ^{n_{k-1}}\cdot a_{k} ^{n_k} Where

n1+n2++nk1+nk=nnn1,n2,n3,nk1,nk0 n_1+n_2+\cdots+n_{k-1}+n_{k} = n \\ n \ge n_1,n_2,n_3\cdots ,n_{k-1},n_{k} \ge 0 n1,n2,n3,nk1,nk Whole numbers  n_1,n_2,n_3\cdots ,n_{k-1},n_{k} \in \text{ Whole numbers }

It is important to observe that number of terms in the expansion is equal to different sets of values of (n1,n2,n3,nk1,nk) \left( n_1,n_2,n_3\cdots ,n_{k-1},n_{k} \right) , which satisfies the above two conditions. To calculate all the permutations . Let us denote all the possible values of the variables n1 n_1 ,n2n_2 and so on as the powers of xx.

x0+x1+x2++xn1+xn \large x^0+x^1+x^{2}+\cdots+x^{n-1}+x^{n}

Multiply the possible values of all the variables \text{Multiply the possible values of all the variables}

(x0+x1+x2++xn)(x0+x1+x2++xn)(x0+x1+x2++xn)k times\underbrace{(x^0+x^1+x^{2}+\cdots+x^{n} )\cdot(x^0+x^1+x^{2}+\cdots+x^{n} )\cdots (x^0+x^1+x^{2}+\cdots+x^{n} )}_{k \text{ times}}

=(x0+x1+x2++xn1+xn)k = (x^0+x^1+x^{2}+\cdots+x^{n-1}+x^{n})^{k}

We want the Sum of variables to be equal to n n . Which means we are trying to find coefficient of xn x^{n} . Using formula of G.P

(x0+x1+x2++xn1+xn)k=(1xn+1)k(1x)kNow Expand (1xn+1)k using binomial expansion (x^{0}+x^1+x^{2}+\cdots+x^{n-1}+x^{n})^{k} = \dfrac{(1-x^{n+1})^{k}}{(1-x)^{k}} \\ \quad \small\color{#3D99F6}{\text{Now Expand }(1-x^{n+1})^{k} \text{ using binomial expansion}}

(1(n1)xn+1+(n2)x2(n+1)+(nn)(1)kxk(n+1)These terms have power >n.We can ignore them)(1x)k \left( 1-\underbrace{\dbinom{n}{1}\cdot x^{n+1}+\dbinom{n}{2}\cdot x^{2(n+1)}-\cdots+\dbinom{n}{n}\cdot (-1)^{k}x^{k(n+1)}}_{\text{These terms have power } > n .\text{We can ignore them} } \right) \cdot \left( 1-x \right)^{-k}

To find coeff. of xn in 1(1x)k \text{To find coeff. of } x^{n} \text{ in } \large \dfrac{1}{(1-x)^k}

1(1x)=r=0xr 0th Derivative (1)(1)1(1x)2=r=0rxr1 1st Derivative (1)(2)(1)2(1x)3=r=0r(r1)xr2 2nd Derivative (1)(2)(3)(1)3(1x)4=r=0r(r1)(r2)xr3 3rd Derivative  \dfrac{1}{(1-x)} = \sum_{r=0}^{\infty} x^{r} \quad \small\color{#3D99F6}{\text{ 0th Derivative }} \\ (-1)\dfrac{(-1)^{1}}{(1-x)^{2}} = \sum_{r=0}^{\infty} rx^{r-1} \quad \small\color{#3D99F6}{\text{ 1st Derivative }} \\ (-1)(-2)\dfrac{(-1)^{2}}{(1-x)^{3}} = \sum_{r=0}^{\infty} r(r-1)x^{r-2} \quad \small\color{#3D99F6}{\text{ 2nd Derivative }} \\ (-1)(-2)(-3)\dfrac{(-1)^{3}}{(1-x)^{4}} = \sum_{r=0}^{\infty} r(r-1)(r-2)x^{r-3} \quad \small\color{#3D99F6}{\text{ 3rd Derivative }}

From the pattern

(1)(2)(3)([k1])(1)k1(1x)k=r=0r(r1)(r2)(rk)xrk+1 (k-1)th Derivative  (-1)(-2)(-3)\cdots(-[k-1]) \dfrac{(-1)^{k-1}}{(1-x)^{k}} = \sum_{r=0}^{\infty} r(r-1)(r-2)\cdots(r-k)x^{r-k+1} \quad \small\color{#3D99F6}{\text{ (k-1)th Derivative }}

(k1)!(1)2(k1)(1x)k=r=0r(r1)(r2)(rk)xrk+11(1x)k=r=0r(r1)(r2)(rk)(k1)!xrk+1 (k-1)! \dfrac{(-1)^{2(k-1)}}{(1-x)^{k}} = \sum_{r=0}^{\infty} r(r-1)(r-2)\cdots(r-k)x^{r-k+1} \\ \dfrac{1}{(1-x)^{k}} = \sum_{r=0}^{\infty} \dfrac{r(r-1)(r-2)\cdots(r-k)}{(k-1)!}x^{r-k+1}

r(r1)(r2)(rk)(k1)! \dfrac{r(r-1)(r-2)\cdots(r-k)}{(k-1)!} is nothing but (rk1) \dbinom{r}{k-1} . To find coeff. of xn x^n put r=n+k1 r=n+k-1

Coefficient of xn x^{n} is given by (n+k1k1) \dbinom{n+k-1}{k-1} or (n+k1n) \dbinom{n+k-1}{n}

Hence proved \large \text{Hence proved}

I hope you enjoyed this note . Thank you.

Note by Sabhrant .
2 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

The ideas that you expressed here can be summarized using the stars and bars approach.

Like you mentioned, we are looking for the number of non-negative integer solutions to the equation

n1+n2++nk=n n_1 + n_2 + \ldots + n_k = n

Calvin Lin Staff - 2 years, 10 months ago

Log in to reply

sweet

Charlotte Milanese - 2 years, 10 months ago

Log in to reply

COOL

Charlotte Milanese - 2 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...