Find the coefficient of $x^{10}$

Question

We have been given the following function.

$f(x)$= $x$ +$x^2$ + $x^4$ + $x^8$ + $x^{16}$ + $x^{32}$ + ...upto infinite terms

The question is as follows:

What is the coefficient of $x^{10}$ in $f(f(x))$?

I tried solving it myself and I found the answer too but the method of solving was too much time-consuming.
I had solved it manually by only considering the first four terms of $f(f(x))$. This method took me about 10 minutes.
But the problem is that this question was asked in a competitive exam called JEE which requires solving the question in max. 3-4 minutes.
So, I wanted to know if there was a faster method to solve this problem.

Thanks in advance.

Answer 1

Note that we may at any point in our calculation ignore any terms of degree $11$ or higher. Therefore we may also ignore any terms whose inclusion will only lead to degree $11$ or higher terms. We have: $$ f(f(x)) = (x + x^2 + x^4 + x^8 + \cdots) + (x + x^2 + x^4 + x^8 +\cdots)^2 \\+ (x + x^2 + x^4 + \cdots)^4 + (x + x^2 + \cdots)^8 + \cdots $$ From here we may look at each of the brackets and simply extract the ones which lead to degree $10$, using the multinomial theorem (basically the binomial theorem) for what it's worth:

• $x + x^2 + x^4 + x^8 + \cdots$: no terms
• $(x + x^2 + x^4 + x^8 + \cdots)^2$: we get $2x^2\cdot x^8$
• $(x + x^2 + x^4 + \cdots)^4$: we get $6 (x)^2\cdot (x^4)^2 + 4(x^2)^3\cdot x^4$
• $(x + x^2 + \cdots)^8$: we get $28(x)^6\cdot(x^2)^2$

where I've used brackets to clarify which terms I've picked in each case.

Answer 2

Since you are looking for $x^{10}$ term, you should ask the question: when would I get $x^{10}$ from $f(x)^n$? When the power $n$ of $x^n$ is too large, it would not work. So considering the first 4 terms is reasonable. But you don't need to expand everything, for example, if you would consider $f(x)+f(x)^2+f(x)^4+f(x)^8$, note that $f(x)=x+x^2+...$ does not contain $x^{10}$. Next we look at $f(x)^2$, which has the form $(x+x^2+...)(x+x^2+...)$, expanding this would give $x^{10}$ if 2 powers add up to 10, this happens for $x^2\cdot x^8=x^{10}$, and we also have the other term from $x^8\cdot x^2$. As for $f(x)^4$, you are always multiplying 4 terms together, so you just need to see if you can get 10 from adding 4 powers, this is possible when $2+2+2+4=10$, but the 4 can be chosen from any other "bracket", so there are 4 such terms. If you understand what I meant, try to figure out whether $f(x)^8$ contains any term of $x^{10}$.

Answer 3

$f(x)$ contains no tenth power.

$f^2(x)$ has $x^2\cdot x^8$, with a coefficient $2$.

$f^4(x)$ has $x\cdot x\cdot x^4\cdot x^4$ with a coefficient $\dfrac{4!}{2!2!}=6$ and $x^2\cdot x^2\cdot x^2\cdot x^4$ with a coefficient $\dfrac{4!}{3!1!}=4$.

$f^8(x)$ has $x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x^2\cdot x^2$ appearing $\dfrac{8!}{6!2!}=28$ times.

Total $40.$

---

Using a CAS,

$$\cdots+40x^{10}+22x^9+16x^8+8x^7+8x^6+6x^5+3x^4+2x^3+2x^2+x$$