# Difficult generating function

Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers.

*I have added the original problem.

• In what context did you encounter this? I'm curious as to its combinatoric interpretation. Jul 23, 2014 at 22:24
• I found it on a forum just like this, nothing else. Jul 23, 2014 at 22:34

Let $[x^n]$ denote "the coefficient of $x^n$".

Observe that $[x^n]$ in $\prod_{k=1}^{\infty} \prod_{a=3}^{6} (1+x^{a^k})$ gives us the number of ways to represent $n\ge 3$ as the sum of pairwise distinct beautiful numbers. Therefore, the problem boils down to proving that $[x^n]>0\ \forall n\ge 3$. First, we make a key observation.

Key: Notice that if $[x^k]>0$ for $k=0,1,2,...,n$ in $a_0+a_1x+\cdots +a_nx^n$, then in order to prove that $[x^k]>0$ for $k=0,1,2,...,n+m$ in $(a_0+a_1x+\cdots +a_nx^n)(1+x^m)$ with $m<n$, we must only prove that it is $>0$ for $(1+x+x^2+\cdots +x^n )(1+x^m)$. This follows by exponent laws. In other words, the conclusion of the problem isn't hurt by reducing all the coefficients in any intermediate step of the expansion to all $1$'s.

Now to attack the main problem. We proceed by induction.

For the base case, we must show that $[x^n]>0$ in $\prod_{k=1}^{1} \prod_{a=3}^{6} (1+x^{a^k})$ for $n=3,4,...,3^1+4^1+5^1+6^1=18$. This follows directly by expansion since $(1+x^3)(1+x^4)(1+x^5)(1+x^6)=1+x^3+x^4+\cdots +x^{18}$ (with the exception of $x^9$ appearing as $2x^9$). It is enough to proceed to the inductive step at this stage, but we will take some time out to quickly show how it will work. To show that $[x^n]>0$ for $n=3,4...,\sum_{i=1}^2 3^i+4^i+5^i+6^i=104$ in $\prod_{k=1}^{2} \prod_{a=3}^{6} (1+x^{a^k})$, then by turning the key (I've been reading too much "Prime Obsession" lately :P ) and the base case, we must only show that it is $>0$ in $(1+x^3+x^4+\cdots +x^{18})(1+x^9)(1+x^{16})(1+x^{25})(1+x^{36})$. We can do this in steps.

For the first step, we do $(1+x^3+x^4+\cdots +x^{18})(1+x^9)=1+x^3+x^4+\cdots +x^{18}+x^9(1+x^3+x^4+\cdots +x^{18})$ $=1+x^3+x^4+\cdots +x^{18}+x^9+x^{10}+\cdots +x^{27}$. Now, since the powers $x^9, x^{10}, ..., x^{18}$ are repeated exactly once, we can omit them once without hurting the desired conclusion (by the key), and end up with $1+x^3+x^4+\cdots +x^{27}$.

Similarly, the second step consists of multiplying this by $1+x^{16}$ to get ("not in practice, but in principle, and by the key"--let this statement be s0) $1+x^3+x^4+\cdots +x^{43}$; this by $1+x^{25}$ to get (s0) $1+x^3+x^4+\cdots +x^{68}$; and finally this by $x^{36}$ to get (s0) $1+x^3+x^4+\cdots +x^{104}$. Thus, $[x^n]>0$ for $n=3,4,...,104$ as required, and we have passed from the base case to the next largest case.

Now for the meat and potatoes of the problem. Assume that the proposition holds for all $3\le n\le \sum_{i=1}^k 3^i+4^i+5^i+6^i$, i.e. $[x^j]>0$ for $j=3,4,...,\sum_{i=1}^k 3^i+4^i+5^i+6^i$ in $\prod_{n=1}^{k} \prod_{a=3}^{6} (1+x^{a^n})$. As before, we multiply by $(1+x^{b^{k+1}})$ for $b=3,4,5,6$ respectively. By the key, it suffices to prove that $[x^n]>0$ for $n=3,4,...,\sum_{i=1}^{k+1} 3^i+4^i+5^i+6^i$ in $(1+x^3+x^4+\cdots +x^{\sum_{i=1}^k 3^i+4^i+5^i+6^i}) \prod_{a=3}^6 (1+x^{a^{k+1}})$. Actually, we should also at this point let $s_k:=\sum_{i=1}^k 3^i+4^i+5^i+6^i$.

$\bf b=3$. We have $(1+x^3+x^4+\cdots +x^{s_k})(1+x^{3^{k+1}})$ $=1+x^3+x^4+\cdots +x^{s_k}+x^{3^{k+1}}(1+x^3+x^4+\cdots +x^{s_k})$ $=1+x^3+x^4+\cdots +x^{s_k}\color{red} + \color{black} x^{3^{k+1}}+x^{3^{k+1}+3}+x^{3^{k+1}+4}+\cdots +x^{s_k+3^{k+1}}$. Since the exponents of $x$ to the right of the $\color{red} +$ after $x^{3^{k+1}}$ go up by $1$ (by inductive hypothesis), and since $s_k>3^{k+1}$ (note that $3^k+4^k+5^k+6^k>3^k+3^k+3^k+0=3^{k+1}$), it follows that the powers of $x^n$ for $n=3^{k+1}, 3^{k+1}+3, ..., s_k$ are repeated; once to the left of $\color{red} +$ and once to the right. By the key, we may ignore these without hurting the conclusion. Furthermore, since the powers to the right of $\color{red} +$ contain all powers of $x$ from $s_k$ to $s_k+3^{k+1}$, it follows that the powers to the right of $\color{red} +$ contain $x^n$ for $n=s_k+1,s_k+2,...,s_k+3^{k+1}$ since they increase by $1$. Putting the left of $\color{red} +$ and the right of $\color{red} +$ together, we end up with $1+x^3+x^4+\cdots +x^{s_k+3^{k+1}}$, and since $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}$ in this expansion, the result follows for the case $b=3$.

It is not hard to see by the key and the case $b=3$ that, in general, $[x^n]>0$ for $n=3,4,...,n+m$ in $(1+x^3+x^4+\cdots +x^n)(1+x^m)$ if and only if $m<n$. Therefore, we can similarly get that $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}$ for $\bf b=4$; $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}+5^{k+1}$ for $\bf b=5$; and $[x^n]>0$ for $n=3,4,...,s_k+3^{k+1}+4^{k+1}+5^{k+1}+6^{k+1}$ for $\bf b=6$.

This completes the induction, and the result follows that $[x^n]>0$ for $n=3,4,...,s_m\ \forall m\in \mathbb{N}$ in $\prod_{k=1}^{m} \prod_{a=3}^{6} (1+x^{a^k})$. In particular, letting $m\rightarrow \infty$ we see that there is a positive number of ways to represent all natural numbers $n\ge 3$ as the sum of pairwise distinct beautiful numbers, as desired.

• Could you include the definition of beautiful numbers you're using? It doesn't show up in a quick google search. Jul 25, 2014 at 15:20
• Could you include it in the answer, I mean? Right now it's only in your link and down here, rather than at the top of the answer. Jul 25, 2014 at 15:30
• Edit your answer and put the definition in your first paragraph? That's all I meant. Jul 25, 2014 at 15:36
• Thanks for your help Arkan Megraoui. I edited it with the link. Jul 26, 2014 at 11:05

It is equivalent to saying that any positive integer can be written as the sum of at most $4$ ones and distinct powers of $3,4,5,6$. We can easily prove this claim by induction, since the property obviously holds for the first four positive integers (we represent them as a sum of ones), so it holds for the first seven positive integers (add a $3$ to the previous representations), so it holds for the first eleven positive integers (add a $4$ to the previous representations), so it holds for the first sixteen positive integers (add a $5$), so it holds for the first twenty-two (add a $6$), so it holds for the first thirty-one (add a $9=3^2$) and so on forever, since: $$3^n+4^n+5^n+6^n \geq 3^n+3^n+3^n+1 > 3^{n+1}.$$

• Do you know if there's any way to approach this on the analytic side? The fact that there's a dense set of zeroes on the unit circle seems to render the usual complex analysis techniques useless. Jul 23, 2014 at 23:27
• I think that the generating function machinery is unnecessary here, it flows just like the combinatorial argument but with a more convoluted notation that just hides the key idea. Jul 25, 2014 at 15:16
• Unnecessary like the downvote. Jul 25, 2014 at 15:18
• For my part, I remain interested in seeing a complex-analytic approach to this. (Though I'm prepared to accept that it's just impossible in this case.) @ArkanMegraoui Jul 25, 2014 at 15:24
• I believe that an analytic solution is possible by a careful study of the distribution of the arguments of the zeroes on the boundary of the unit ball. However, any analytic approach (or Banach/H density approach, or saddle point method approach) would just give that any $n$ big enough can be represented as a sum of at most four ones and different powers of 3,4,5,6. Just like killing flies with a shotgun, since the argument is trivial by induction. Jul 25, 2014 at 15:28