Combinatorics: Partitioning Generating Functions

[Shoney45]

Homework Statement

Show with generating functions that every positive integer can be written as a unique power of 2.

Homework Equations

The generating function for a_r, the number of ways to write an integer r as a sum of distinct powers of 2 = g(x) = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...(1 + x^2k)...

The Attempt at a Solution

This is an example from the text that is pretty crucial to understanding this section of my text. The book then goes on to say the following:

"To show that every integer can be written as a unique sum of distinct powers of 2, we must show that the coefficient of every power of x in g(x) is 1. That is, show that:

g(x) = 1 + x + x^2 + x^3 + ...= 1/(1-x)".

1) So my first problem is that I don't understand why g(x) is changing. The actual generating function is for powers of two. But for the above identity, the author is using the standard identity for the polynomial expansion of 1/(1-x)

I don't get it.

2) The identity [1 + x + x^2 + x^3 + ... = 1/(1-x)] can also be expressed as (1-x)*g(x) = 1. This is achieved by repeatedly using the factorization (1-x^k)(1+x^k) = 1-x^2k such that:

(1-x)*g(x) = (1 - x)(1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...
= (1 - x^2)(1 + x^2)(1 + x^4)(1 + x^8)...
= (1 - x^4)(1 + x^4)(1 + x^8)...
.
.
.
= 1

My problem is that I can't understand how to make the final step that sets (1-x)*g(x) = 1. By my reckoning, if I keep on applying the identity, then I will keep on getting powers of (1 - x^2k), and I don't understand how that eventually becomes 1.

 

[mighty2000]

Hello,

Thank you for your post and for your questions. I understand your confusion about the generating function for powers of 2 and the use of the standard identity for polynomial expansion. Let me try to explain it in a different way.

The generating function g(x) = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...(1 + x^2k)... is actually a representation of the powers of 2. Each term in the product, (1 + x^2k), represents the number of ways to write k as a sum of distinct powers of 2. For example, (1 + x^4) represents the number of ways to write 4 as a sum of distinct powers of 2, which is 1 (since 4 can only be written as 2^2).

Now, when we multiply all these terms together, we are essentially adding up all the different ways to write any positive integer as a sum of distinct powers of 2. So, g(x) represents the generating function for all the powers of 2.

Now, the identity [1 + x + x^2 + x^3 + ... = 1/(1-x)] can be used to show that every integer can be written as a unique sum of distinct powers of 2. This is because when we multiply (1-x) with g(x), we are essentially removing the terms that represent the same power of 2. For example, (1-x)(1+x^2) will remove the term (1+x^2) from (1+x)(1+x^2), leaving us with just (1+x), which represents the number of ways to write 1 as a sum of distinct powers of 2.

By repeatedly using this factorization, we will eventually be left with just the term 1, which represents the number of ways to write 0 as a sum of distinct powers of 2. This means that every integer has a unique representation as a sum of distinct powers of 2, since we have removed all the duplicate terms.

I hope this helps to clarify the use of the generating function and the identity. Let me know if you have any further questions or need more clarification. Keep up the good work!