Why Does This Infinite Product Identity Hold for Integer Partitions?

  • Thread starter Thread starter futurebird
  • Start date Start date
  • Tags Tags
    Infinite Product
futurebird
Messages
270
Reaction score
0

Homework Statement


I am reading about integer partitions. I'm learning a proof and I don't understand what would seem to be a simple step... as the book presents it without comment:

\prod_{n=1}^{\infty} \frac{1-q^{2n}}{1-q^{n}}=\prod_{n=1}^{\infty} \frac{1}{1-q^{2n-1}}

The fractions presented are not algebraically equivalent outside of the infinite product... So, it's something about the product that makes this possible. I also know that |q|<1... What is going on?
 
Physics news on Phys.org
Look at a partial product:

\left(\frac{1-q^2}{1-q}\right)\left(\frac{1-q^4}{1-q^2}\right)\left(\frac{1-q^6}{1-q^3}\right)\left(\frac{1-q^8}{1-q^4}\right)...

At least intuitively, each factor in the numerator is canceled by the corresponding factor in the denominator with q to that same even exponent. So in the limit you are left with 1 on top and odd powers of q in the factors on the bottom.
 
Thank you so much... I wish I'd seen that, it makes so much sense.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top