7
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Commented Dec 24, 2018 at 9:46
  • $\begingroup$ I tried but for $k\gt 2 $ it gets fuzzy $\endgroup$ Commented Dec 24, 2018 at 9:48
  • $\begingroup$ oeis.org/A166984 $\endgroup$
    – user140541
    Commented Dec 24, 2018 at 9:50
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Dec 24, 2018 at 9:56
  • $\begingroup$ @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. $\endgroup$
    – fantasie
    Commented Dec 24, 2018 at 10:10

3 Answers 3

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you so much, I like this theory for speeding up the calculation so much! $\endgroup$ Commented Dec 24, 2018 at 13:13
2
$\begingroup$

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}

$\endgroup$
6
  • $\begingroup$ I' sorry I do not understand the solution as I have not yet done recursions. $\endgroup$ Commented Dec 24, 2018 at 10:16
  • $\begingroup$ @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)}. $$ $\endgroup$
    – user140541
    Commented Dec 24, 2018 at 10:24
  • $\begingroup$ The answer seems correct $\endgroup$ Commented Dec 24, 2018 at 10:26
  • $\begingroup$ $c(k)=\frac{16^k-4^k}{12}$ $\endgroup$ Commented Dec 24, 2018 at 10:31
  • $\begingroup$ @AleksasDomarkas Thnx. $\endgroup$
    – user140541
    Commented Dec 24, 2018 at 10:38
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .