# Find the coefficient of $x^{10}$

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.

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.

• From writing up my expression of $f(f(x))$ and listing the degree-10 terms from each bracket, this shouldn't take that much time. It really depends on how much you have to write in your answer. If you have to write it out like here (or even more detailed), then 10 minutes to solve this problem isn't unreasonable. If you only have to write the final answer, then much of what I've written here may be skipped in your own notes, and you will get at the answer that much quicker. Commented Oct 16, 2018 at 7:21
• Thanks a lot for such a fast answer. I did "almost" exactly what you did. When I said ten minutes, it included the time taken to come up with a method as well. Commented Oct 16, 2018 at 17:21
• Also, I am new to Stack Exchange. I didn't expect my question to be a answered within an hour of posting the question. It would have taken weeks if I had asked this on Quora. Commented Oct 16, 2018 at 17:23

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}$$.

$$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$$

• Crossed with Arthur.
– user65203
Commented Oct 16, 2018 at 7:22