Problem. Consider the recursion relation: $$a_{n+1} = (a_n - 2)^2; a_0 = x$$ Find the coefficient of \(x^2\) in \(a_n\).
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