• Support PF! Buy your school textbooks, materials and every day products Here!

Combinatorics - Binomial Theorem Questions

  • Thread starter mattmns
  • Start date
  • #1
1,085
6
There are a few questions that have been giving me trouble with this binomial theorem stuff.

(1). Using the binomial theorem and the relation [tex](1+x)^{m_1} (1+x)^{m_2} = (1+x)^{m_1 + m_2}[/tex]

prove that:

[tex]\sum_{k=0}^n \binom{m_1}{k} \binom{m_2}{n-k} = \binom{m_1 + m_2}{n}[/tex]

(2). Prove by induction on n that, for n a positive integer,

[tex]\frac{1}{(1-z)^n} = \sum_{k=0}^\infty \binom{n+k-1}{k}z^k, |z| < 1.[/tex]

Assume the validity of

[tex]\frac{1}{(1-z)} = \sum_{k=0}^\infty z^k, |z| < 1.[/tex]

-----------------------

For (1). This is very easy to prove using a combinatorial argument, but I am just not seeing how I can prove it with the binomial theorem. I have been pluggin them in getting the sums, but nothing is clicking. This problem may be similar to the problem with the other problem (mixing of sums?)

For (2). The base case is obvious, practically assumed. But I am not sure where to go with the following:

After some basic maniuplation I get:

[tex]\frac{1}{(1-z)^{n+1}} = \left(\sum_{k=0}^\infty \binom{n+k-1}{k}z^k\right)\left(\sum_{1=0}^\infty z^i \right)[/tex]

Can I mix these two together somehow?

My goal is to get the above equation equal to [tex]\sum_{k=0}^\infty \binom{n+k}{k}z^k\right)\left[/tex]

Any hints or ideas on either of the problems? Thanks!
 
Last edited:

Answers and Replies

  • #2
Galileo
Science Advisor
Homework Helper
1,989
6
In both cases you have to multiply sums. If you multiply two polynomials, you get another polynomial:

[tex]\sum \limits_{k=0}^{m_1} a_kx^k\cdot\sum \limits_{k=0}^{m_2} b_kx^k=\sum \limits_{k=0}^{m_1+m_2} c_kx^k[/tex]
First find out how c_k is related to the coefficients a_i and b_i. After that, it's plug and play for both exercises.
 

Related Threads on Combinatorics - Binomial Theorem Questions

  • Last Post
2
Replies
44
Views
3K
  • Last Post
2
Replies
29
Views
6K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
2
Views
708
Top