Maths Olympiad Prep

Library / /238 of 348

Algebra Difficulty 5.0 AIME, harder Find the answer

Let f(x)=x2+2x+1f(x)=x^{2}+2 x+1. Let g(x)=f(f(⋯f(x)))g(x)=f(f(\cdots f(x))), where there are 2009f s2009 f \mathrm{~s} in the expression for g(x)g(x). Then g(x)g(x) can be written as g(x)=x22009+a22009−1x22009−1+⋯+a1x+a0g(x)=x^{2^{2009}}+a_{2^{2009}-1} x^{2^{2009}-1}+\cdots+a_{1} x+a_{0} where the aia_{i} are constants. Compute a22009−1a_{2^{2009}-1}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

22009f(x)=(x+1)22^{2009} f(x)=(x+1)^{2}, so f(xn+cxn−1+…)=(xn+cxn−1+…+1)2=x2n+2cx2n−1+…f\left(x^{n}+c x^{n-1}+\ldots\right)=\left(x^{n}+c x^{n-1}+\ldots+1\right)^{2}=x^{2 n}+2 c x^{2 n-1}+\ldots. Applying the preceding formula repeatedly shows us that the coefficient of the term of second highest degree in the polynomial doubles each time, so after 2009 applications of ff it is 220092^{2009}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.