# Center of Math Problem of the Week, 2018-01-30

Problem. Consider the recursion relation: $$a_{n+1} = (a_n - 2)^2; a_0 = x$$ Find the coefficient of $$x^2$$ in $$a_n$$.

Source (via zemkat).

Solution. If we work directly in the polynomial ring $$\mathbb{Z}[x]$$, the polynomial expressions will quickly become cumbersome. However, the only coefficients of $$a_n$$ that can affect the coefficient of $$x^2$$ in $$a_{n+1}$$ are those of degree 2 or lower. So instead we will work in the polynomial ring $$\mathbb{Z}[x]/(x^3)$$.

Let $$A_n$$, $$B_n$$, and $$C_n$$ denote the coefficients of $$a_n$$ of degree 2, 1, and 0, respectively. Then $$A_0 = 0$$, $$B_0 = 1$$, $$C_0 = 0$$, and we can compute recurrence relations for these sequences from the recursion for $$a_n$$. Specifically, \begin{align} a_{n+1} &= (a_n - 2)^2 \\ &= (A_n x^2 + B_n x + (C_n - 2))^2 \\ &= (B_n^2 + 2A_n(C_n - 2))x^2 + 2B_n(C_n - 2)x + (C_n - 2)^2\pmod{x^3}. \end{align}

Hence \begin{align} A_{n+1} &= B_n^2 + 2A_n(C_n - 2); \\ B_{n+1} &= 2B_n(C_n - 2); \text{and} \\ C_{n+1} &= (C_n - 2)^2. \end{align} Now let's analyze these sequences. The sequence $$(C_n)$$ is the simplest: $$C_0 = 0$$ and $$C_1 = (-2)^2 = 4$$, which is a fixed point of the function $$(x - 2)^2.$$ Hence $$C_n = 4$$ for any $$n \ge 1.$$

Next, let's look at $$B_n$$. The expression $$C_n - 2$$ is $$-2$$ when $$n = 0$$ and 2 otherwise. Hence $$B_1 = -4B_0$$ and $$B_{n+1} = 4B_n$$ if $$n \ge 1,$$ that is, $$B_n = -4^n$$ for $$n \ge 1.$$

Finally, we analyze $$A_n$$. If $$n \ge 1$$, then from our above observations it follows that \begin{align} A_{n+1} &= B_n^2 + 2A_n(C_n - 2) \\ &= (-4^n)^2 + 4A_n \\ &= 4A_n + 16^n. \end{align} Moreover, $$A_1 = 1 = 4\cdot 0 + 16^0,$$ so this recurrence relation holds for all $$n.$$ Now we apply a little generatingfunctionology. Let $$A(x) = \sum_{n\ge 0} A_n x^n.$$

Then \begin{align} A(x) &= \sum_{n\ge 0} A_n x^n \\ &= a_0 + \sum_{n\ge 0} (4A_n + 16^n) x^{n+1} \\ &= 4x A(x) + \frac{x}{1 - 16x}, \end{align} that is, $$A(x) = \frac{x}{(1 - 16x)(1 - 4x)}.$$

By performing partial fraction decomposition, we find that $$A(x) = \frac{1}{12}\left(\frac{1}{1 - 16x} - \frac{1}{1 - 4x}\right).$$ Hence it follows that the $$x^2$$ coefficient of $$a_n$$ is $$A_n = \frac{16^n - 4^n}{12}.$$

writing by M Slone. other writing