# 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}$

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.

• Have you tried checking the results for the initial few values of $k$ to see if there is any pattern? Note I haven't done this myself so I don't know if it'll help or not. Commented Dec 24, 2018 at 9:46
• I tried but for $k\gt 2$ it gets fuzzy Commented Dec 24, 2018 at 9:48
• oeis.org/A166984
– user140541
Commented Dec 24, 2018 at 9:50
• @d.k.o. I'm sorry I know what OEIS is but I am looking for a method not the solution, I'm more interested in the how. Commented Dec 24, 2018 at 9:56
• @PrakharNagpal d.k.o means that the answer is the numbers from that oeis sequence. By the way, I have examined the first a few terms, and it matches. Commented Dec 24, 2018 at 10:10

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

• Thank you so much, I like this theory for speeding up the calculation so much! Commented Dec 24, 2018 at 13:13

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}

• I' sorry I do not understand the solution as I have not yet done recursions. Commented Dec 24, 2018 at 10:16
• @PrakharNagpal You have the solution for $a(k)$. Plug it into the equation for $b(k)$ and you easily get $-4^k$. Then you plug these solutions into the third equation: $$c(k)=4c(k-1)+4^{2(k-1)}.$$
– user140541
Commented Dec 24, 2018 at 10:24
• The answer seems correct Commented Dec 24, 2018 at 10:26
• $c(k)=\frac{16^k-4^k}{12}$ Commented Dec 24, 2018 at 10:31
• @AleksasDomarkas Thnx.
– user140541
Commented Dec 24, 2018 at 10:38

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.