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
 A: 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}+...$
A: 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}$
A: For a polynomial
$$\sum_{n=0}^{\infty}c_n x^n$$
you find coefficient at $x^n$ as
$$c_n=\frac1{n!}f^{(n)}(f(0))$$
Now if you have a composite function $f(g(x))$ there is a well-known expression, Faà di Bruno's formula, which can be reduced to something simpler for your case.
In general if $f(x)=\sum\limits_{n=0}^{\infty}a_n x^n$ and $g(x)=\sum\limits_{n=0}^{\infty}b_n x^n$ then
$$f(g(x))=\sum_{n=0}^{\infty}c_n x^n$$
where
$$c_n=\sum_{i \in P_n}^{\infty}a_k\prod_{i=1}^{k}b_{i_k}$$
$$P_n=\{(i_1,i_2,\cdots,i_k) : 1 \leq k \leq n, \sum_{m=1}^{k} i_m=n \}$$
Applied to your case
$$c_{10}=\sum_{i \in P_{10}}^{\infty}a_k\prod_{i=1}^{k}a_{i_k}$$
$$P_{10}=\{(i_1,i_2,\cdots,i_k) : 1 \leq k \leq 10, \sum_{m=1}^{k} i_m=10 \}$$
But all your $a_n=0$ unless $n=2^m$ when $a_n=1$
Which is to say in how many ways you can uniquely represent $10$ as a sum of $1,2,4,8$ using $1,2,4,8$ terms.
That counting or similar you cannot avoid.
A: To cut it short, for $x^{10}$ to appear in $f(x)^n$, you just need to have some $2^k$'s add up to 10. It doesn't necessarily require binary expansions.
