Yes, but I don't see why we should include the empty set in counting. So I think it should be 2^k-1. Is it because in n =rm^2 we need to also throw in the possibility that no prime occurs in the factorization of r because r = 1? Also, I would like to see a proof that n can always be written as rm^2. That's not clear to me.
As for representation of integers as the product of a squarefree integer and a square : Suppose is the canonical representation of as a product of prime-powers. Using the division algorithm, write , , for . Then , where is squarefree and . I'll let you show that this representation is unique.
If you know a bit about algebra, we can state this situation in more abstract terms. Consider (excluding ) as a commutative monoid. The set of powers is a sub-monoid, and the quotient monoid is isomorphic to to (this is actually a group, since every element in this monoid has finite order at most ). In the case , which is your case, the monoid can in fact be considered as a countably infinite vector space over the field with two elements.
Thanks! That clears up all of my problems. Now, I'm studying another proof of Erdos. This time, the proof of Bertrand's postulate. I'm following wikipedia's outline of the argument. I've made it quite far without getting confused. However, I don't understand the part that says " When p > sqrt(2n), the number (2n, n) has at most one factor of p. I would like to see a proof of that. Second, I don't see how that plays into the following argument using Lemma 2.