Finding the coefficient of $x^2$ in $\tiny{\left(\left(\left(\left(x-2\right)^2-2\right)^2-2\right)^2-\cdots-2\right)^2}$

Question

Find the coefficient of $x^2$ in the expansion of $$\underbrace{\left(\left(\left(\left(x-2\right)^2 -2\right)^2 -2\right)^2 -\cdots -2\right)^2}_{k\;\text{times}}$$I tried to equate it to a polynomial of the form $$\underbrace{P_k x^3}_{\text{Terms of power}\geq3} + \underbrace{B_kx^2}_{\text{Terms of power=2}} + \underbrace{A_k x} _{\text{Terms of power=1}} +C$$So we can write$$\underbrace{\left(\left(\left(\left(x-2\right)^2 -2\right)^2 -2\right)^2 -\cdots -2\right)^2}_{k\;\text{times}} = P_k x^3 + B_kx^2 + A_k x +C$$ We can find $C$ easily if we simply set $x=0$ in the original equation and we get, $$\underbrace{\left(\left(\left(\left(0-2\right)^2 -2\right)^2 -2\right)^2 -\cdots -2\right)^2}_{k\;\text{times}} = \underbrace{\left(\ldots \left(\left(4-2\right)^2 -2\right)^2-\cdots-\cdots 2\right)^2}_{k-1 \;\text{times}}$$ Simplifying till the end we get, $$C=4$$ So we get, $$\underbrace{\left(\left(\left(\left(x-2\right)^2 -2\right)^2 -2\right)^2 -\ldots -2\right)^2}_{k\;\text{times}} = P_k x^3 + B_kx^2 + A_k x +4$$ Not sure where to go from here.
EDIT: I think I have found a solution to develop the recursion, please tell me if it is right.
$$P_k x^3 +B_kx^2 + A_k x +C=\underbrace{\left(\left(\left(\left(x-2\right)^2 -2\right)^2 -2\right)^2 -\cdots -2\right)^2}_{k\;\text{times}}$$ Now, we can also write it as $$P_k x^3 +B_kx^2 + A_k x +C=\left[\underbrace{\left(\ldots \left(\left(x-2\right)^2-2\right)^2 \ldots -2\right)^2}_{k-1\;\text{times}} -2\right]^2$$ Which is
$$P_k x^3 +B_kx^2 + A_k x +C=\left[\left(P_{k-1}x^3 + B_{k-1}x^2 + A_{k-1} x+ 4\right)-2\right]^2$$ $$P_k x^3 +B_kx^2 + A_k x +C=\left(P_{k-1}x^3 + B_{k-1}x^2 + A_{k-1} x+ 2\right)^2$$ So, we get, $$P_k x^3 +B_kx^2 + A_k x +C=\left(P^2_{k-1}x^6+ 2P_{k-1}B{k-1}x^5 + \left(2P_{k-1}A_{k-1}B^2_{k-1}\right)x^4 + \left(4P_{k-1} + 2B{k-1}A{k-1}\right)x^3 + + \left(4B_{k-1} + A^2_{k-1}\right)x^2 + 4A_{k-1}x + 4\right)$$ Thus, we get, $$A_k = 4A_{k-1}$$ And, $$B_k = A^2_{k-1} + 4B_{k-1}$$ Since $\left(x-2\right)^2 = x^2 - 4x + 4$ we have $A_1 = -4$ and similarly $A_2 = -4\cdot4=-4^2$ and in general $$A_k=-4^k$$ Now, we can use the relation we have for $B_k = A^2_{k-1} + 4B_{k-1}$ Writing this as $$B_k = A^2 _{k-1} + 4B_{k-1} = Ak^2 _{k-1} + 4\left(A^2_{k-2} + 4B_{k-2}\right)$$ $$B_k = A^2_{k-1} + 4A^2_{k-2} + 4^2\left(A_{k-3}^2 + 4B_{k-3}\right)$$ So, $$B_k = A^2_{k-1} + 4A^2_{k-2} + 4^2A^2_{k-3} + \ldots 4^{k-2}A_1^2 + 4^{k-1}B_1$$ Then we can substitute, $B_1 = 1, A_1 = 4, A_2 = -4^2, A_3 = -4^3, \ldots A_{k-1}= -4^{k-1}$ We get, $$B_k = 4^{2k-2} + 4\cdot4^{2k-4} + 4^2\cdot4^{2k-6} + \ldots + 4^{k-2}\cdot4^2 + 4^{k-1}\cdot 1$$ $$B_k = 4^{2k-2} + 4^{2k-3} + 4^{2k-4} + \ldots 4^{k+1} + 4^k + 4^{k-1}$$ $$B_k = 4^{k-1}\left(1 + 4+4^2+4^3 + \ldots 4^{k-2} + 4^{k-1}\right)$$ $$B_k = 4^{k-1} \cdot \frac{4^k - 1}{4-1} = \frac{4^{2k-1} - 4^{k-1}}{3}$$ This is how I have solved it but I am wondering if there is a nicer solution.

Answer 1

If we note $f_k(x)=\underbrace{\left(\left(\left(\left(x-2\right)^2 -2\right)^2 -2\right)^2 -\cdots -2\right)^2}_{k\;\text{times}}=x^3Q_k(x)+R_k(x)$ with $\deg R_k\le 2$

Then we are only interested in the following induction:

$$R_{k+1}(x)=(R_k(x)-2)^2\pmod{x^3}$$ When squaring and taking the remainder of the division by $x^3$ you get $$(ax^2+bx+c-2)^2\pmod{x^3}=(b^2+2ac-4a)x^2+(2bc-4b)x+(c^2-4c+4)$$

Note that $c_0=0$ and $c_1=0-0+4=4$ and $c_2=16-16+4=4$, so except for its first term, the sequence $(c_n)_n$ is constant and $\forall i>0,\ c_i=4$.

Applying this simplification we get: $$(b^2+4a)x^2+4bx+4$$

The induction s then $P_0(x)=x$ : $\begin{cases}a_0=0\\b_0=1\\c_0=0\end{cases}\quad$ and $\quad P_n(x)$ : $\begin{cases}a_n=b_{n-1}^2+4a_{n-1}\\b_n=4b_{n-1}\\c_n=4\end{cases}$

The coefficient $b_n$ resolves easily to $b_n=4^n$

• Method 1 :

For $a_n$ you can go directly to $a_n-4a_{n-1}=\frac 1{16}16^n$ which solves to $a_n=hom_n+part_n$

The homogeneous general solution is $hom_n=\alpha 4^n$

And a particular solution with RHS has to be found under the form $part_n=\beta 16^n$ since $4\neq 16$.

• Method 2 :

We are linearising the equation for $a_n$.

$a_n=b_{n-1}^2+4a_{n-1}=16b_{n-2}^2+4a_{n-1}=16(a_{n-1}-4a_{n-2})+4a_{n-1}=20a_{n-1}-64a_{n-2}$

You get the linear equation with constant coefficients : $$a_n-20a_{n-1}+64a_{n-2}=0$$

Whose characteristic equation $r^2-20r+64=0$ gives roots $r=4$ and $r=16$.

So both methods give in the end $$a_n=\alpha 4^n + \beta 16^n$$

Solving for $a_0=0$ and $a_1=1$ we get $$a_n=\frac{16^n-4^n}{12}$$

---

So overall except for notations we used the same method. Good job!

I find your text a bit confusing, but your calculations are perfectly fine.

• For instance once you have determined that terms in $x^3$ are not needed, do not carry everywhere $P_kx^3$, work only on the remainder like I did.
• Also your choice of $Bx^2+Ax+C$ is weird, why swapping the meaning of $A$ and $B$ in regards to usual quadratics $(ax^2+bx+c)$ ?
• Finally I have nothing against caps but inherently here $4$ and $A$ have close graphs in this font, which do not ease the reading.

In the end, the resolution for my $a_n$ or your $B_k$ can be speeded up by using the theory on linear inductive sequences:

https://en.wikipedia.org/wiki/Constant-recursive_sequence

Finally as suggested by J.Omielan and d.k.o, it is a good idea to calculate the first terms and then go to OEIS, it sometimes helps the problem resolution to know the closed formula for the coefficients in advance.

https://oeis.org/A166984

Answer 2

You need to solve the following recursion: $$ \begin{cases} a_k=(a_{k-1}-2)^2, \\ b_k=b_{k-1}a_{k-1}, \\ c_k=c_{k-1}a_{k-1}+b_{k-1}^2 \end{cases} $$ with $a_1=4,b_1=-4,c_1=1$ ($a_k,b_k,c_k$ correspond to the coefficients of the constant term, $x$, and $x^2$, respectively).

The solution is \begin{align} a_k=4, \quad b_k=-4^k,\quad c_k=4^{k-1}(4^k-1)/3. \end{align}

Answer 3

Here is the idea that might work.

Denote the polynomial from the original post as $F_k(x)$. Lemma. The following identity holds: $$ F_k(4\cos^2 t)=4\cos^2 2^kt. $$ The lemma can be easily proved via induction and formula $\cos 2x=2\cos^2x-1$. Therefore, we nee to find the coefficient $a_k$ in the following expansion: $$ 4\cos^2 2^kt=\sum_{j=0}^{2^k} a_j\cdot (4\cos^2t)^{j}. $$ In other words, $a_j$ are almost the coefficients of the $2^{k+1}$-th Chebyshev's polynomial of the first kind.