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.

closed as off-topic by B. Mehta, user302797, Peter Taylor, Severin Schraven, Claude Leibovici Apr 26 at 8:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – B. Mehta, user302797, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • The question as written makes no sense to me. Did you intend to ask something like "How can I show using generating functions that every positive integer has a unique partition as a sum of powers of 3 with no part occurring more than twice?"? – Peter Taylor Apr 26 at 7:28

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.

  • The series at the bottom clearly diverges for $x>-1$; therefore, a restriction should be placed. – ProtectedSource Apr 26 at 3:26
  • @ProtectedSource : Generating functions are formal power series -- in fact they are accounting devices. Convergence is irrelevant as $x$ is not a variable that is specialized to a value. – Eric Towers Apr 26 at 3:38

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.

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