Coefficient of $x^{10}$ in $f(f(x))$

Let $f\left( x \right) = x + {x^2} + {x^4} + {x^8} + {x^{16}} + {x^{32}}+ ..$, then the coefficient of $x^{10}$ in $f(f(x))$ is _____.

My approach is as follow

$f\left( {f\left( x \right)} \right) = f\left( x \right) + {\left( {f\left( x \right)} \right)^2} + {\left( {f\left( x \right)} \right)^4} + {\left( {f\left( x \right)} \right)^8} + ..$

Let $T = f\left( x \right);U = {\left( {f\left( x \right)} \right)^2};V = {\left( {f\left( x \right)} \right)^4};W = {\left( {f\left( x \right)} \right)^8}$

Let the coefficient of $x^{10}$ in $T $ is zero

Taking U

${\left( {f\left( x \right)} \right)^2} = {\left( {x + {x^2} + {x^4} + {x^8} + ..} \right)^2}$

Hence the coefficient of $x^{10}$ in $U$ is $2x^{10}$ hence $2$

For $V$ and $W$ it is getting complicated hence any short cut or easy method to solve it

Solution 1:

We have $$f(f(x))=f(x)+f(x)^2+f(x)^4+f(x)^8+f(x)^{16}+\ldots$$ To find the coefficient of $x^{10}$ in this expansion, note that the smallest power of $f(x)^k$ for some $k$ is $x^k$.

Hence, to find the coefficient of $x^{10}$, we only need to consider $$f(x)+f(x)^2+f(x)^4+f(x)^8$$ The coefficient of $x^{10}$ in $f(x)^k$ represents the number of solutions to $$\sum_{i=1}^k a_i=10$$ Where $a_i$ are integral powers of $2$.

We can systematically find these solutions using the binary representation of $10_{10}=1010_2$

If we are a little hand wavy with how we use binary representation, we can say that $10_{10}$ $$=1010_2$$ $$=210_2=1002_2$$ $$=130_2=202_2$$ Note that the expressions in the $i^\text{th}$ line represent the different ways to represent $10$ as a sum of $i+1$ integral powers of $2$ e.g. in the second line we have $210_2\implies 10=4+4+2$. We created the expressions in a line by recursively taking the expressions from the previous line and splitting a single power of $2$ in half.

We then have to account for permutations. Clearly $f(x)$ has no coefficient of $x^{10}$

The coefficient of $x^{10}$ in $f(x)^2$ is the number of permutations of $\{8,2\}$, which is $2!=\boxed{2}$.

The coefficient of $x^{10}$ in $f(x)^4$ is the number of permutations of $\{4,2,2,2\}$ and $\{4,4,1,1\}$, which is $\frac{4!}{3!}+\frac{4!}{2!2!}=\boxed{10}$.

The coefficient of $x^{10}$ in $f(x)^8$ is not as easily found using the recursive method we used before. However, it is easily found that the only way to express $10$ as the sum of $8$ powers of $2$ is $1+1+1+1+1+1+2+2$. There are $\frac{8!}{6!2!}=\boxed{28}$ permutations of this.

Hence, the total coefficient of $x^{10}$ is $2+10+28=\boxed{40}$

Solution 2:

Let's replace $10$ with a lower number, $5$, and illustrate the role of partitions in the result.

Only $f+f^2+f^4$ contributes to the coefficient of $x^5$. The $f$ term has none, of course.

The $f^2=f\cdot f$ term contributes a coefficient of $2$ from $x^1\cdot x^4$ and $x^4\cdot x^1$. Note that we get two terms because one contribution has $x^4$ from the first factor and the other has the $x^4$ factor coming from the second $f$ factor. Ordering of the partitions is important.

The $f^4$ term contributes a coefficient of $4$ which comes from $x^2\cdot x^3$ and $x^3\cdot x^2$ in the square of $f^2$. We get a contribution of $4$ here because the $x^3$ factor from $f^2$ had a coefficient of $2$ in $f^2$, which in turn came from $x^1\cdot x^2$ and $x^2\cdot x^1$ in the square of $f$.

So, the total of six terms in $x^5$, therefore a coefficient of $6$, came from the following partitions:

$5 = 1+4$ (from $f^2$)

$5 = 4+1$ (from $f^2$)

$5 = (1+1)+(1+2)$ (from $f^4$, with the parentheses showing the separate inputs to $f^4$ from $f^2$)

$5 = (1+1)+(2+1)$ (from $f^4$)

$5 = (1+2)+(1+1)$ (from $f^4$)

$5 = (2+1)+(1+1)$ (from $f^4$)

In other words:

• We picked partitions into powers of $2$, corresponding to the powers of $x$ in $f$.

• We picked those partitions where the number of terms is also a power of $2$, from the powers of $f$ you use in the outer function evaluation.

• For each partitioning satisfying the criteria above, we count all the distinguishable orderings.

Now try this partition scheme using $10$ as the input. There could be $1,2,4,$ or $8$ powers of $2$ in the partition, and for each partition that has different powers of $2$ there will be multiple orderings to count as we saw with the $x^5$ coefficient above.

We have $8+2$ with $2$ orderings, $4+4+1+1$ with six orderings, $4+2+2+2$ with four orderings, and $2+2+1+1+1+1+1+1$ with $28$ orderings. Thus the coeficient of $x^{10}$ will be $40$.

The entire series begins as

$x+2x^2+2x^3+3x^4+6x^5+8x^6+8x^7+16x^8+22x^9+\text{[spoiler]}x^{10}+...$

Solution 3:

I will do the computation explicitly, then check with the engine. It is enough to work in the field of polynomials in $\Bbb Q[x]$ taken modulo (the ideal generated by) $x^{11}$. We are composing polynomial functions $f,g$ that map $0$ to $0$, $f(0)=0$, $g(0)=0$, and there is a small computation to be done to show that changing either $f$, or $g$ (or both) by elements of the ideal $(x^{11})$ lead to the same result for $f\circ g$ before and after the change(s).

Lef now $f$ be $f=x+x^2+x^4+x^8+O(x^{11})$. Then, as in the OP and in the comments, $$ \begin{aligned} f(f(x)) &= f(x) + f(x)^2 + f(x)^4 + f(x)^8 + O(x^{11})\ , \\ f(x) &= x\Big(1+x+x^3+x^7\Big) + O(x^{11}) \\ f(x)^2 &= x^2\Big(1+x+x^3+x^7\Big)^2 + O(x^{11}) \\ &=x^2\Big(1+x^2+x^6 \ + \ 2x+2x^3+2x^7\ + \ 2x^4+2x^8\Big) + O(x^{11})\\ &=x^2\Big(1 + 2x + x^2 + 2x^3 + 2x^4 + x^6 + 2x^7 + 2x^8\Big) + O(x^{11}) \\ f(x)^4 &= (f(x)^2)^2\\ &=x^4\Big(1 + 2x + x^2 + 2x^3 + 2x^4 + x^6\Big)^2 + O(x^{11})\\ &=x^4\Big(1 + 4x^2 + x^4 + 4x^6\ + \ 4x+ 2x^2 + 4x^3 + 4x^4+2x^6\\ &\qquad + 4x^3 + 8x^4 + 8x^5 \ + \ 4x^5 + 4x^6\Big) + O(x^{11})\\ &=x^4\Big(1 + 4x + 6x^2 + 8x^3 + 13x^4 + 12x^5 + 10x^6\Big) + O(x^{11}) \\ f(x)^8 &= (f(x)^4)^2\\ &=x^8\Big(1 + 4x + 6x^2\Big)^2 +O(x^{11})\\ &=x^8\Big(1 + 16x^2 \ + \ 8x + 12 x^2\Big)^2 +O(x^{11})\\ &=x^8\Big(1 + 8x + 28x^2 \Big)^2 +O(x^{11})\ . \end{aligned} $$ Now we can extract the coefficient of $x^{10}$ from $f\circ f=f+f^2+f^4+f^8$, it is $$ 0 + 2 + 10 + 28=40\ . $$

Well, i typed the above to show it can be easily done with bare hands. However, if there is no structure found in there, then the solution is a computation (not an insight, in its essence), so why not use the engine for this task? Here are some ways to get the result in sage. Dialogues with the sage interpreter are shown, the dialogues are easily translated in a human, mathematical language, an advantage of sage (and of many other computer algebra systems..).

sage: R.<x> = PowerSeriesRing(QQ, default_prec=11)
sage: f = x + x^2 + x^4 + x^8 + O(x^11)
sage: f^2 + O(x^11)
x^2 + 2*x^3 + x^4 + 2*x^5 + 2*x^6 + x^8 + 2*x^9 + 2*x^10 + O(x^11)
sage: f^4 + O(x^11)
x^4 + 4*x^5 + 6*x^6 + 8*x^7 + 13*x^8 + 12*x^9 + 10*x^10 + O(x^11)
sage: f^8 + O(x^11)
x^8 + 8*x^9 + 28*x^10 + O(x^11)
sage: f + f^2 + f^4 + f^8 + O(x^11)
x + 2*x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 8*x^6 + 8*x^7 + 16*x^8 + 22*x^9 + 40*x^10 + O(x^11)

Of course, the one-liner is also possible (after introducing the ring R)...

sage: f(f(x)) + O(x^11)
x + 2*x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 8*x^6 + 8*x^7 + 16*x^8 + 22*x^9 + 40*x^10 + O(x^11)