I have to show using generating functions that decimal expansion of non-negative integer is unique. So I created generating function:

$$ \prod_{k=0}\sum_{i=0}^9 {x^{i \cdot 10^k}} $$

I have to show that coefficient of every power of $x$ is equal to $1$. In other word I have to show that constructed generating function is equal to $\sum_{i=0}x^i$. I am completely helpless maybe there is some simpler way?

  • $\begingroup$ As is frequently discussed, $0.999\ldots = 1.000\ldots$. I'm not sure what technique you're using, so maybe it accounts for this case, but if not, it won't work. $\endgroup$ – Henry Swanson Mar 28 '14 at 19:18
  • $\begingroup$ @HenrySwanson I meant non-negative integer. I have corrected the question. $\endgroup$ – Trismegistos Mar 28 '14 at 19:20

Suppose we restrict ourselves to $m+1$-digit integers. Then the generating function becomes $$f_m(x) = \prod_{k=0}^m \sum_{j=0}^9 x^{j 10^k}.$$ Evaluating the sum this is $$f_m(x) = \prod_{k=0}^m \frac{x^{10\times 10^k} - 1}{x^{10^k}-1} = \prod_{k=0}^m \frac{x^{10^{k+1}} - 1}{x^{10^k}-1}.$$ This product telescopes and the only terms left over are $$f_m(x) = \frac{x^{10^{m+1}}-1}{x-1}.$$ But this is a geometric series and $$f_m(x) = \sum_{q=0}^{10^{m+1}-1} x^q.$$ QED.

  • $\begingroup$ Whole proof is coded in two words "product relescopes" :D. I already know the answer anyway. $\endgroup$ – Trismegistos Apr 4 '14 at 15:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.