Maths Olympiad Prep

Library / /247 of 353

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.