Polynomials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Polynomials

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#1 h Apr 25, 2025, 2:05 AM

Y by

Define a family of polynomials by $P_{0}(x) = x - 2$ and $P_{k}(x) = \left(P_{k - 1} (x)\right)^2 - 2$ if $k \geq 1$ then find the coefficient of $x^2$ in $P_{k}(x)$ in terms of $k.$

This post has been edited 2 times. Last edited by P162008, Apr 25, 2025, 2:06 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12 posts

#2 h Apr 25, 2025, 8:29 AM • 1 Y

Y by P162008

The answer is $\frac{4^{k-1}(4^k - 1)}{3}$ . Call $L_k, C_k, Q_k$ the linear, constant, and quadratic coefficients respectively of $P_k(x)$ . Clearly, $Q_k = 2Q_{k - 1}C_{k - 1} + L_{k - 1}^2$ for all $k \geq 1$ by polynomial multiplication. It is easy to show that $C_k = 2$ for all $k \geq 1$ using induction since $C_1 = 2$ . This combined with the fact that $Q_0 = 0$ and $L_0 = 1$ gives us $Q_k = 4Q_{k - 1} + L_{k - 1}^2$ for all $k \geq 1$ . Additionally, $L_k = 2L_{k - 1}C_{k - 1} = 4L_{k - 1}$ for all $k \geq 2$ and since $L_1 = -4$ , $L_k = -4^k$ for all $k \geq 1$ . This combined with $L_0 = 1$ and $Q_0 = 0$ gives $Q_k = 4Q_{k - 1} + L_{k - 1}^2 = 4Q_{k - 1} + 4^{2k - 2}$ . We will show next with induction that $Q_k = \frac{4^{k-1}(4^k - 1)}{3}$ for all $k \geq 0$ .

Base Case: Since k = 0, $\frac{4^{0 - 1}(4^0 - 1)}{3} = 0$ which is true since $P_0$ is linear.
Inductive Step: I.H.: Assume the formula holds true for k. Since $k + 1 \geq 1$ , $Q_{k + 1} = 4Q_{k} + 4^{2k}$ . By I.H., $Q_{k + 1} = 4 \cdot \frac{4^{k - 1}(4^k - 1)}{3} + 4^{2k} = \frac{4^k(4^k - 1) + 3 \cdot 4^{2k}}{3} = \frac{4^k((4 - 1) \cdot 4^k + 4^k - 1)}{3} = \frac{4^k(4^{k + 1} - 4^k + 4^k - 1)}{3} = \frac{4^k(4^{k + 1} - 1)}{3}$ as desired. By principle of mathematical induction, the formula holds true for all $k \geq 0$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a