0
$\begingroup$

Question:

Show with generating functions that every positive integer has a unique decimal representation.

Attempt:

I've come up with the following to represent the ones, tens, hundreds, so on:

$(1+x^1+x^2+...+x^9)(1+x^{10}+x^{20}+..+x^{90})(1+x^{100}+...+x^{900})$.

I then get this for my generating function:

$\frac{(1-x^{10})(1-x^{100})(1-x^{1000})...}{(1-x)(1-x^{10})(1-x^{100})...}$

Even then, I'm not sure if I'm doing the problem correctly.

Edit:

Just realized that the terms cancel out so I get:

$\frac{1}{(1-x)}$

I'm stuck here now. I know I need to get something like $12 = 1*10^1 + 2*10^0$, but I don't know how to do that with generating functions.

$\endgroup$
  • 1
    $\begingroup$ Not sure if infinite products is the intended approach, but note that if you continued with your approach, a lot of terms will cancel and you will get $\frac{1}{1-x} = 1 + x + x^2 + \cdots$ as desired. $\endgroup$ – angryavian Oct 16 '18 at 19:23
  • $\begingroup$ @angryavian Didn't notice that. Now I'm stuck with the decimal representation part. $\endgroup$ – cosmicbrownie Oct 16 '18 at 19:36
  • 1
    $\begingroup$ Then you are done because the coefficient of $x^n$ is $1$ for each nonnegative integer $n$. (If there were multiple decimal representations of $n$, then the coefficient would be $> 1$.) $\endgroup$ – angryavian Oct 16 '18 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.