Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4997. feladat (2018. december)

B. 4997. Tekintsük egész együtthatós polinomok következő \(\displaystyle p_n(x)\) sorozatát: legyen \(\displaystyle p_0(x)=0\), \(\displaystyle p_1(x)=1\), és minden \(\displaystyle n\ge 2\) esetén

\(\displaystyle p_n(x)=p_{n-1}(x)+x\cdot p_{n-2}(x). \)

Bizonyítsuk be, hogy ha valamilyen \(\displaystyle n\), \(\displaystyle m\) pozitív egészekre egy \(\displaystyle f(x)\) polinom osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomnak, akkor a \(\displaystyle p_{(m,n)}(x)\) polinomnak is osztója.

(\(\displaystyle (n,m)\) jelöli az \(\displaystyle n\) és \(\displaystyle m\) legnagyobb közös osztóját. A \(\displaystyle P(x)\) polinom osztója a \(\displaystyle Q(x)\) polinomnak, ha van olyan \(\displaystyle R(x)\) valós együtthatós polinom, amelyre \(\displaystyle Q(x)= P(x)R(x)\).)

(6 pont)

A beküldési határidő 2019. január 10-én LEJÁRT.


Megoldás. Először néhány egyszerű észrevételt igazolunk.

Teljes indukcióval adódik a rekurzió segítségével, hogy \(\displaystyle n\geq 1\) esetén \(\displaystyle p_n(x)\) olyan egész együtthatós polinom, melynek konstans tagja 1.

Mivel \(\displaystyle 0<n\)-re \(\displaystyle p_n\) konstans tagja 1, ezért ekkor \(\displaystyle x\nmid p_n(x)\). Ebből teljes indukcióval következik, hogy két, a sorozatban egymást követő polinom mindig relatív prím: legnagyobb közös osztójuk konstans polinom. Ha ugyanis \(\displaystyle f(x)\mid p_{n-1} (x)\) és \(\displaystyle f(x)\mid p_{n}(x)\), akkor a rekurzió alapján \(\displaystyle f(x)\mid xp_{n-2}(x)\), amiből \(\displaystyle x\nmid f(x)\) miatt (ami teljesül, hiszen \(\displaystyle x\) nem osztja a \(\displaystyle p_n(x)\) polinomokat \(\displaystyle n>1\) mellett) \(\displaystyle f(x)\mid p_{n-2}\) következik. Ezt a lépést ismételgetve pedig végül \(\displaystyle f(x)\mid p_1(x)=1\)-hez jutunk. Tehát a sorozat szomszédos tagjainak legnagyobb közös osztója konstans.

Először megmutatjuk, hogy \(\displaystyle 2\leq k\leq n-1\) esetén

\(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x). \)\(\displaystyle {(*)}\)

Ha \(\displaystyle k=2\), akkor a feltétel a megadott rekurzió alapján teljesül, hiszen \(\displaystyle p_3(x)=x+1\), és így valóban

\(\displaystyle p_{2}(x)p_{n-1}(x)+(p_{3}(x)-p_2(x))p_{n-2}(x)=p_{n-1}(x)+xp_{n-2}(x)=p_n(x).\)

Ha az állítást \(\displaystyle k\)-ra már igazoltuk, akkor a rekurziót használva

\(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)

\(\displaystyle =p_{k}(x)(p_{n-k}(x)+xp_{n-k-1}(x))+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)

\(\displaystyle =p_{k+1}(x)p_{n-k}(x)+xp_k(x)p_{n-k-1}(x)=p_{k+1}(x)p_{n-k}(x)+(p_{k+2}(x)-p_{k+1}(x))p_{n-k-1}(x),\)

vagyis az állítás \(\displaystyle k+1\)-re is teljesül. Tehát indukcióval következik, hogy minden \(\displaystyle 2\leq k\leq n-1\) mellett teljesül a \(\displaystyle (*)\) állítás.

Most megmutatjuk, hogy ha \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, és mondjuk \(\displaystyle n\geq m\), akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)\) polinomnak is. Innen az állítás már következik, ugyanis az euklideszi algoritmust követve ilyen lépésekkel előbb-utóbb eljutunk oda, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_{(m,n)}(x)\) polinomnak is.

Írjuk fel \(\displaystyle (*)\)-ot \(\displaystyle k=n-m\) választással:

\(\displaystyle p_n(x)=p_{n-m}(x)p_{m+1}(x)+(p_{n-m+1}(x)-p_{n-m}(x))p_{m}(x).\)

Ebből leolvasható, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)p_{m+1}(x)\) polinomnak is.

Most felhasználjuk, hogy \(\displaystyle p_m\) és \(\displaystyle p_{m+1}\) relatív prímek, és így \(\displaystyle f(x)\mid p_m(x)\) miatt \(\displaystyle f\) és \(\displaystyle p_{m+1}\) is azok: legnagyobb közös osztójuk konstans. Így \(\displaystyle f(x)\mid p_{n-m}(x)p_{m+1}(x)\) oszthatóságból következik, hogy \(\displaystyle f(x)\mid p_{n-m}(x)\) is teljesül.

Ebből pedig a korábbiak szerint az euklideszi algoritmust követve adódik, hogy \(\displaystyle f(x)\) valóban osztója \(\displaystyle p_{(m,n)}(x)\) polinomnak is.


Statisztika:

A B. 4997. feladat értékelése még nem fejeződött be.


A KöMaL 2018. decemberi matematika feladatai