Polynomials $(P_n(X))_{n\in\mathbb{N}}$ are defined as: $$P_0(X)=0, \quad P_1(X)=X+2,$$$$P_n(X)=P_{n-1}(X)+3P_{n-1}(X)\cdot P_{n-2}(X)+P_{n-2}(X), \quad (\forall) n\geq2.$$Show that if $ k $ divides $m$ then $P_k(X)$ divides $P_m(X).$
Problem
Source: Moldova TST 2023
Tags: algebra, polynomial
07.04.2023 18:21
augustin_p wrote: Polynomials $(P_n(X))_{n\in\mathbb{N}}$ are defined as: $$P_0(X)=0, \quad P_1(X)=X+2,$$$$P_n(X)=P_{n-1}(X)+3P_{n-1}(X)\cdot P_{n-2}(X)+P_{n-2}(X), \quad (\forall) n\geq2.$$Show that if $ k $ divides $m$ then $P_k(X)$ divides $P_m(X).$ Easy to find (and easier to prove with induction) that $P_n(x)=\frac{(3x+7)^{F_n}-1}3$ where $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$ is the fibonacci sequence. Then result follows immediately from $F_n|F_{mn}$ $\forall m,n\in\mathbb Z_{>0}$
07.04.2023 18:56
pco wrote: augustin_p wrote: Polynomials $(P_n(X))_{n\in\mathbb{N}}$ are defined as: $$P_0(X)=0, \quad P_1(X)=X+2,$$$$P_n(X)=P_{n-1}(X)+3P_{n-1}(X)\cdot P_{n-2}(X)+P_{n-2}(X), \quad (\forall) n\geq2.$$Show that if $ k $ divides $m$ then $P_k(X)$ divides $P_m(X).$ Easy to find (and easier to prove with induction) that $P_n(x)=\frac{(3x+7)^{F_n}-1}3$ where $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$ is the fibonacci sequence. Then result follows immediately from $F_n|F_{mn}$ $\forall m,n\in\mathbb Z_{>0}$ How do you find $P_n(x)=\frac{(3x+7)^{F_n}-1}3$ ?
07.04.2023 19:05
Mathlover_1 wrote: How do you find $P_n(x)=\frac{(3x+7)^{F_n}-1}3$ ? Write $3P_n(x)+1=(3P_{n-1}(x)+1)(3P_{n-2}(x)+1)$ And from $u_{n}=u_{n-1}u_{n-2}$, you get $u_{n}=u_{n-2}^2u_{n-3}$ $=u_{n-3}^3u_{n-4}^2$ ... $=u_1^{F_n}u_0^{F_{n-1}}$ So $3P_n(x)+1=(3P_1(x)+1)^{F_n}(3P_0(x)+1)^{F_{n-1}}$ $=(3x+7)^{F_n}$
07.04.2023 19:15
pco wrote: Mathlover_1 wrote: How do you find $P_n(x)=\frac{(3x+7)^{F_n}-1}3$ ? Write $3P_n(x)+1=(3P_{n-1}(x)+1)(3P_{n-2}(x)+1)$ And from $u_{n}=u_{n-1}u_{n-2}$, you get $u_{n}=u_{n-2}^2u_{n-3}$ $=u_{n-3}^3u_{n-4}^2$ ... $=u_1^{F_n}u_0^{F_{n-1}}$ So $3P_n(x)+1=(3P_1(x)+1)^{F_n}(3P_0(x)+1)^{F_{n-1}}$ $=(3x+7)^{F_n}$ Thanks a lot
09.04.2023 19:37
Straight from 2008 Mediterranean Mathematical Competition.