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

Binomial Theorem

  • Thread starter saubbie
  • Start date
13
0
1. Homework Statement

I am trying to find the number of nonnegative integer solutions to a+2b+4c=10^30. I found a generating function, and need to check the coefficient of 10^30.

2. Homework Equations

The generating function is 1/((1-x)(1-x^2)(1-x^4)). I found the PFD, which is -1/(8(x-1)^3) + 1/(4(x-1)^2) - 9/(32(x-1)) + 1/(16(1+x)^2) + 5/(32(1+x)) + (1+x)/(8(1+x^2))

3. The Attempt at a Solution

I need to simplify this into an equation using the Binomial Theorem. In class, we related each individual fraction to a series of some sort, or a combination and then combined them all into one equation, but I do not understand it at all. Please help!
 

Answers and Replies

743
1
You do know how to use the binomial theorem in this case right? Expand each of those fractions as a formal power series. Since the exponent is negative, they expand according to

[tex] (1-x)^{-k} = \displaystyle \sum_{n \geq 0} {{n+k-1} \choose {n}} x^n [/tex]

then in order to find the coefficient of [itex] x^m [/itex] (which I will denote [itex] \left[ x^m \right] [/itex]) you need to find [itex] \left[ x^m \right] [/itex] for each individual fraction and then add them up. Think of each fraction as a power series that you're adding, then [itex] \left[ x^m \right] [/itex] will just be the coefficient when you add like terms.

This is going to be a long and disgusting process, but it's entirely doable.

Edit: I think I made a mistake in my original post. My other way just ended up simplifying to the original problem because the exponent of the power series expansion in each case was only 1. It's best just to do it the long way above.
 
Last edited:
743
1
Using a CAS, I found the coefficient of [itex] 10^{30} [/itex] to be 62500000000000000000000000000500000000000000000000000000001
 
Last edited:

Related Threads for: Binomial Theorem

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
2
Views
679
  • Last Post
Replies
6
Views
888
  • Last Post
Replies
23
Views
4K
  • Last Post
Replies
1
Views
3K
Top