How to find generating function that every positive integer can be written as a unique sum of powers of 3

Question

How to find generating functions that every positive integer can be written as a unique sum of powers of 3, such that each power of 3 is used at most twice.

Answer 1

I believe you are talking about numbers in base $3$. Each positive integer can be denoted by a unique sum of powers of $3$ multiplied by either $0$, $1$, or $2$. For example,

$$10=1\cdot3^0+0\cdot3^1+1\cdot3^2=(101)_3$$

It can be shown that this works for every number like so:

Consider $n\in\mathbb{W}$. $\forall n<3^1,n=n\cdot3^0$. Once $n$ has reached $3^1$, we need the next power of $3$ being $3^1$. So for $3$ we can just add on $3^1$: $3=0\cdot3^0+1\cdot3^1$. And from there we can continue the cycle until we reach the next power of 3. And this pattern can be repeated forever.

Answer 2

We allow $0$, $1$, or $2$ of $3^0$s. And then $0$, $1$, or $2$ of $3^1$s. And then $0$, $1$, or $2$ of $3^2$s. And then $0$, $1$, or $2$ of $3^3$s. And then $0$, $1$, or $2$ of $3^4$s. And then $0$, $1$, or $2$ of $3^5$s. ...

With generating functions, we want the power of $x$ be the quantity we are counting. So when we say "$1$ of $3^4$" above, we want a contribution of $x^{1 \cdot 3^4}$.

\begin{align*} 3^0&: x^0+x^1+x^2 \\ 3^1&: x^0+x^3+x^6 \\ 3^2&: x^0+x^{1 \cdot 3^2}+x^{2 \cdot 3^2} \\ 3^3&: x^0+x^{1 \cdot 3^3}+x^{2 \cdot 3^3} \\ &\vdots \end{align*}

Since we wish to allow one choice from each row, we take their product. Then we simplify, using properties of finite geometric series (or, in this case, the difference of cubes factorization) and telescoping. \begin{align*} \prod_{i=0}^\infty (x^{0 \cdot 3^i} + x^{1 \cdot 3^i} + x^{2 \cdot 3^i}) &= \prod_{i=0}^\infty (1 + (x)^{3^i} + (x^2)^{3^i}) \\ &= \prod_{i=0}^\infty \frac{1- (x^3)^{3^i}}{1 - (x)^{3^i}} \\ &= \prod_{i=0}^\infty \frac{1- (x)^{3^{i+1}}}{1 - (x)^{3^i}} \\ &= \frac{1- (x)^{3^{0+1}}}{1 - (x)^{3^0}} \cdot \frac{1- (x)^{3^{1+1}}}{1 - (x)^{3^1}} \cdot \frac{1- (x)^{3^{2+1}}}{1 - (x)^{3^2}} \cdots \\ &= \frac{1}{1-(x)^1} \\ &= 1 + x+ x^2 + x^3 + \cdots \end{align*} So we see every power of $x$ has coefficient $1$. For each term, the coefficient counts the number of ways to write the power as a sum of $0$, $1$, or $2$ of $3^0$s, $0$, $1$, or $2$ of $3^1$s, $0$, $1$, or $2$ of $3^2$s, $0$, $1$, or $2$ of $3^3$s, ... We get a coefficient of $1$ for every non-negative power of $x$, so there is only one way to write each non-negative integer as such a sum.