Maths Olympiad Prep

Library / /17 of 121

Algebra Difficulty 5.4 AIME, harder Prove it India

Problem:
Define a sequence ⟨f0(x),f1(x),f2(x),…⟩\langle f_{0}(x), f_{1}(x), f_{2}(x), \ldots \rangle of functions by
f0(x)=1,f1(x)=x,(fn(x))2−1=fn+1(x)fn−1(x), for n≥1 f_{0}(x)=1, \quad f_{1}(x)=x, \quad (f_{n}(x))^{2}-1=f_{n+1}(x) f_{n-1}(x), \text{ for } n \geq 1
Prove that each fn(x)f_{n}(x) is a polynomial with integer coefficients.

Solution

Solution:
Observe that
fn2(x)−fn−1(x)fn+1(x)=1=fn−12(x)−fn−2(x)fn(x) f_{n}^{2}(x)-f_{n-1}(x) f_{n+1}(x)=1=f_{n-1}^{2}(x)-f_{n-2}(x) f_{n}(x)
This gives
fn(x)(fn(x)+fn−2(x))=fn−1(fn−1(x)+fn+1(x)) f_{n}(x)\left(f_{n}(x)+f_{n-2}(x)\right)=f_{n-1}\left(f_{n-1}(x)+f_{n+1}(x)\right)
We write this as
fn−1(x)+fn+1(x)fn(x)=fn−2(x)+fn(x)fn−1(x) \frac{f_{n-1}(x)+f_{n+1}(x)}{f_{n}(x)}=\frac{f_{n-2}(x)+f_{n}(x)}{f_{n-1}(x)}
Using induction, we get
fn−1(x)+fn+1(x)fn(x)=f0(x)+f2(x)f1(x) \frac{f_{n-1}(x)+f_{n+1}(x)}{f_{n}(x)}=\frac{f_{0}(x)+f_{2}(x)}{f_{1}(x)}
Observe that
f2(x)=f12(x)−1f0(x)=x2−1 f_{2}(x)=\frac{f_{1}^{2}(x)-1}{f_{0}(x)}=x^{2}-1
Hence
fn−1(x)+fn+1(x)fn(x)=1+(x2−1)x=x \frac{f_{n-1}(x)+f_{n+1}(x)}{f_{n}(x)}=\frac{1+\left(x^{2}-1\right)}{x}=x
Thus we obtain
fn+1(x)=xfn(x)−fn−1(x) f_{n+1}(x)=x f_{n}(x)-f_{n-1}(x)
Since f0(x),f1(x)f_{0}(x), f_{1}(x) and f2(x)f_{2}(x) are polynomials with integer coefficients, induction again shows that fn(x)f_{n}(x) is a polynomial with integer coefficients.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.