Feladat:	Pontversenyen kívüli P.355	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Megyesi Gábor ,  Zsilinszky László
Füzet:	1983/április, 166 - 169. oldal		PDF  |  MathML
Témakör(ök):	Oszthatóság, Egész együtthatós polinomok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1981/december: Pontversenyen kívüli P.355

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. $\begin{array}{c}{\displaystyle \frac{a_1^k}{p_1}+\frac{a_2^k}{p_2}+\text{...}+\frac{a_n^k}{p_n}\mathrm{.}}\end{array}$ (1) Megoldás. Első lépésként a $k\leqq n-2$ esettel foglalkozunk. Belátjuk, hogy ez esetben a kifejezés értéke $0$. Bővítsük mindegyik törtet úgy, hogy a $p_n$ kifejezés szerepeljen a nevezőben: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle \frac{a_1^k}{p_1}}& {\displaystyle =-\frac{\left(a_n-a_2\right)\left(a_n-a_3\right)\text{...}\left(a_n-a_{n-1}\right)a_1^k}{\left(a_1-a_2\right)\left(a_1-a_3\right)\text{...}\left(a_1-a_{n-1}\right)p_n}}\hfill \\ \hfill {\displaystyle \frac{a_2^k}{p_2}}& {\displaystyle =-\frac{\left(a_n-a_1\right)\left(a_n-a_3\right)\text{...}\left(a_n-a_{n-1}\right)a_2^k}{\left(a_2-a_1\right)\left(a_2-a_3\right)\text{...}\left(a_2-a_{n-1}\right)p_n}}\hfill \\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle \frac{a_i^k}{p_i}}& {\displaystyle =-\frac{\left(a_n-a_1\right)\text{...}\left(a_n-a_{i-1}\right)\left(a_n-a_{i+1}\right)\text{...}\left(a_n-a_{n-1}\right)a_i^k}{\left(a_i-a_1\right)\text{...}\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right)\text{...}\left(a_i-a_{n-1}\right)p_n}}\hfill \\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle \frac{a_{n-1}^k}{p_{n-1}}}& {\displaystyle =-\frac{\left(a_n-a_1\right)\text{...}\left(a_n-a_{n-2}\right)a_{n-1}^k}{\left(a_{n-1}-a_1\right)\text{...}\left(a_{n-1}-a_{n-2}\right)p_n}\mathrm{.}}\hfill \end{array}}$ Tekintsük a következő polinomokat: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle q_1\left(x\right)}& {\displaystyle =\left(x-a_2\right)\left(x-a_3\right)\text{...}\left(x-a_{n-1}\right)\mathrm{,}\text{...}\mathrm{,}}\hfill \\ \hfill {\displaystyle q_i\left(x\right)}& {\displaystyle =\left(x-a_1\right)\text{...}\left(x-a_{i-1}\right)\left(x-a_{i+1}\right)\text{...}\left(x-a_{n-1}\right)\mathrm{,}\text{...}\mathrm{,}}\hfill \\ \hfill {\displaystyle q_{n-1}\left(x\right)}& {\displaystyle =\left(x-a_1\right)\text{...}\left(x-a_{n-2}\right)\mathrm{.}}\hfill \end{array}}$ $\begin{array}{c}{\displaystyle \left(\text{Vagyis legyen }Q\left(x\right)=\left(x-a_1\right)\left(x-a_2\right)\text{...}\left(x-a_{n-1}\right)\text{ és }{q}_i\left(x\right)=\frac{Q\left(x\right)}{x-a_i}\right)\mathrm{.}}\end{array}$ Nyilvánvaló, hogy $\frac{a_i^k}{p_i}=-\frac{a_i^k}{p_n}\frac{q_i\left(a_n\right)}{q_i\left(a_i\right)}$ és akkor az (1) kifejezés $\begin{array}{c}{\displaystyle \frac{a_1^k}{p_1}+\text{...}+\frac{a_n^k}{p_n}=\frac{1}{p_n}\left(a_n^k-\frac{q_1\left(a_n\right)}{q_1\left(a_1\right)}{a}_1^k-\frac{q_2\left(a_n\right)}{q_2\left(a_2\right)}{a}_2^k-\text{...}-\frac{q_{n-1}\left(a_n\right)}{q_{n-1}\left(a_{n-1}\right)}{a}_{n-1}^k\right)\mathrm{.}}\end{array}$ (2) Itt a zárójelben az alábbi $P\left(x\right)$ polinomnak az $x=a_n$ helyen felvett értéke áll: $\begin{array}{c}{\displaystyle P\left(x\right)=x^k-\frac{q_1\left(x\right)}{q_1\left(a_1\right)}{a}_1^k-\frac{q_2\left(x\right)}{q_2\left(a_2\right)}{a}_2^k-\text{...}-\frac{q_{n-1}\left(x\right)}{q_{n-1}\left(a_{n-1}\right)}{a}_{n-1}^k\mathrm{.}}\end{array}$ Itt $k\leqq n-2$, a $q_i$ polinomok $\left(n-2\right)$-edfokúak, a nevezők rögzített helyettesítési értékek, $a_i^k$ szintén konstans, $P\left(x\right)$ tehát egy (legfeljebb) $\left(n-2\right)$-edfokú polinom. Belátjuk, hogy $P$ helyettesítési értéke az $x=a_1$, $a_2$, $\text{...}$, $a_{n-1}$ helyeken rendre $0$. Legyen $1\leqq i\leqq n-1$. $a_i$ egyaránt gyöke a $q_1\left(x\right)$, $\text{...}$, $q_{i-1}\left(x\right)$, $q_{i+1}\left(x\right)$, $\text{...}$, $q_{n-1}\left(x\right)$ polinomoknak [hiszen ezek mindegyikében szerepel az $\left(x-a_1\right)$ tényező], tehát $q_j\left(a_i\right)=0$, ha $j\ne i$. Következésképp $\begin{array}{c}{\displaystyle P\left(a_i\right)=a_i^k-\frac{q_i\left(a_i\right)}{q_i\left(a_i\right)}{a}_i^k=a_i^k-a_i^k=\mathrm{0,}}\end{array}$ ahogy állítottuk. Az $a_1$, $a_2$, $\text{...}$, $a_{n-1}$ számok mind különbözők, így azt kaptuk, hogy a legföljebb $\left(n-2\right)$-edfokú $P\left(x\right)$ polinomnak $n-1$ különböző helyen felvett értéke $0$. Ebből viszont, mint ismeretes, már következik, hogy $P\left(x\right)$ csak az azonosan $0$ polinom lehet. Másrészt (2) szerint $\begin{array}{c}{\displaystyle \frac{a_1^k}{p_1}+\text{...}+\frac{a_n^k}{p_n}=\frac{P\left(a_n\right)}{p_n}\mathrm{,}}\end{array}$ így ennek a kifejezésnek is $0$ az értéke, ahogy állítottuk.   Vizsgáljuk ezután a $k\geqq n-1$ esetet. Legyen $j\leqq n$-re ${\displaystyle \begin{array}{c}\hfill {\displaystyle \frac{a_1^k}{\left(a_1-a_2\right)\left(a_1-a_3\right)\text{...}\left(a_1-a_j\right)}+\frac{a_2^k}{\left(a_2-a_1\right)\left(a_2-a_3\right)\text{...}\left(a_2-a_j\right)}+\text{...}+}\hfill \\ \hfill {\displaystyle +\frac{a_j^k}{\left(a_j-a_1\right)\text{...}\left(a_j-a_{j-1}\right)}=F_{k\mathrm{,}j}\mathrm{.}}\hfill \end{array}}$ $j=2$ esetében $F_{k\mathrm{,2}}=\frac{a_1^k-a_2^k}{a_1-a_2}$ ami mindig egész, ha $a_1$, $a_2$ egész. Másrészt az előzőekben beláttuk, hogy $F_{k\mathrm{,}j}=0$, ha $k\leqq j-2$ (ha az $a$ számok száma legalább $2$-vel nagyobb $k$-nál). Most megmutatjuk, hogy ha $j\geqq 3$, és $k\geqq 1$, akkor $\begin{array}{c}{\displaystyle F_{k\mathrm{,}j}=F_{k-\mathrm{1,}j-1}+a_j{F}_{k-\mathrm{1,}j}}\end{array}$ (3) amiből $k$-ra és $j$-re vonatkozó kettős teljes indukcióval azonnal kapjuk, hogy ha $a_1\mathrm{,}\text{...}\mathrm{,}{a}_n$ mind egészek, akkor $F_{k\mathrm{,}j}$ értéke minden $k\geqq 0$, $j\geqq 2$ értékre egész. (3)-ból ugyanis látszik, hogy ha $F_{k-\mathrm{1,}j}$ és $F_{k-\mathrm{1,}j-1}$ értéke egész, akkor $F_{k\mathrm{,}j}$ értéke is egész. Hátra van még (3) bizonyítása. Legyen $i<j$. Ekkor ${\displaystyle \begin{array}{cc}\hfill {\displaystyle \frac{a_i^k}{\left(a_i-a_1\right)\text{...}\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right)\text{...}\left(a_i-a_j\right)}=}\hfill & \text{(<mn>4</mn>)}\\ \hfill {\displaystyle =\frac{a_i^{k-1}\left(a_i-a_j\right)+a_j{a}_i^{k-1}}{\left(a_i-a_1\right)\text{...}\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right)\text{...}\left(a_i-a_j\right)}=}\hfill \\ \hfill {\displaystyle =\frac{a_i^{k-1}}{\left(a_i-a_1\right)\text{...}\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right)\text{...}\left(a_i-a_{j-1}\right)}+}\hfill \\ \hfill {\displaystyle +a_j\frac{a_i^{k-1}}{\left(a_i-a_1\right)\text{...}\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right)\text{...}\left(a_i-a_j\right)}\mathrm{.}}\hfill \end{array}}$ Végül $\begin{array}{c}{\displaystyle \frac{a_j^k}{\left(a_j-a_1\right)\left(a_j-a_2\right)\text{...}\left(a_j-a_{j-1}\right)}=0+a_j\frac{a_j^{k-1}}{\left(a_j-a_1\right)\left(a_j-a_2\right)\text{...}\left(a_j-a_{j-1}\right)}\mathrm{.}}\end{array}$ (4') Ha most (4) és (4') bal oldalait összeadjuk, akkor éppen $F_{k\mathrm{,}j}$-t kapjuk, ha pedig a jobb oldalakat adjuk össze, akkor $F_{k-\mathrm{1,}j-1}+a_j{F}_{k-\mathrm{1,}j}$ adódik. Ezzel (3)-at és a feladat állítását is beláttuk.   Megjegyzések. 1. Elég egyszerűen belátható, hogy ha az (1) kifejezésben közös nevezőre hozunk, akkor a nevező az összes $\left(a_i-a_j\right)$ alakú tényezők szorzata $\left(i\ne j\right)$, és a számláló minden $i\ne j$-re többszöröse $\left(a_i-a_j\right)$-nek. Abban a ritka esetben, amikor az összes $a_i-a_j$ relatív prím egymáshoz, ebből már következik, hogy a nevezőben szereplő szorzattal is osztható a számláló, vagyis a kifejezés egész szám. Az általános esetben át kell előbb térni $n$-változós polinomokra: az $a_i$-ket határozatlanoknak kell venni, s úgy belátni, hogy a számláló minden $a_i-a_j$ alakú polinommal osztható. Polinomok körében már igaz, hogy ez esetben a polinom az összes ilyen $a_i-a_j$ alakú tényezők szorzatával, azaz a nevezővel is osztható. Ez a többváltozós polinomokra vonatkozó állítás azonban lényegesen mélyebb tételeken alapszik, mint amilyent a fenti bizonyításban használtunk. 2. Gyakran találkozunk a következő, úgynevezett interpolációs feladattal. Meg kell határozni azt a legkisebb fokú polinomot, amely az adott $a_1$, $a_2$, $\text{...}$, $a_{n-1}$ helyeken rendre az adott $c_1$, $c_2$, $\text{...}$, $c_{n-1}$ értékeket veszi fel. A feladat megoldásában szereplő $q_i\left(x\right)$ polinomok segítségével könnyen felírható egy $\left(n-2\right)$-ed fokú megfelelő $R\left(x\right)$ polinom: $\begin{array}{c}{\displaystyle R\left(x\right)=c_1\frac{q_1\left(x\right)}{q_1\left(a_1\right)}+c_2\frac{q_2\left(x\right)}{q_2\left(a_2\right)}+\text{...}+c_{n-1}\frac{q_{n-1}\left(x\right)}{q_{n-1}\left(a_{n-1}\right)}\mathrm{.}}\end{array}$ Valóban láttuk, hogy $q_i\left(a_i\right)=0$, ha $i\ne j$, tehát $R\left(a_i\right)=c_i\frac{q_i\left(a_i\right)}{q_i\left(a_i\right)}=c_i$, ahogy kívántuk. Az $R\left(x\right)$ polinom $\left(n-2\right)$-edfokú (ez az ún. Lagrange-féle interpoláris polinom), és belátható, hogy általában alacsonyabb fokú polinom nem adható meg. 3. A (3) képletből levezethető, hogy $k=n-1$ esetén $F_{k\mathrm{,}n}$ értéke $1$. Ha ugyanis $n=2$, akkor $\begin{array}{c}{\displaystyle F_{n-\mathrm{1,}n}=F_{\mathrm{1,2}}=\frac{a_1}{a_1-a_2}+\frac{a_2}{a_2-a_1}=\mathrm{1,}}\end{array}$ ha pedig $n\geqq 3$, akkor (3) szerint $\begin{array}{c}{\displaystyle F_{n-\mathrm{1,}n}=F_{n-\mathrm{2,}n-1}+a_j{F}_{n-\mathrm{2,}n}\mathrm{.}}\end{array}$ De itt $F_{n-\mathrm{2,}n}=0$, mint láttuk, tehát $F_{n-\mathrm{1,}n}=F_{n-\mathrm{2,}n-1}$. Ebből teljes indukcióval $F_{n-\mathrm{1,}n}=F_{\mathrm{1,2}}=1$ adódik. Másrészt $n\geqq k$ esetén teljes indukcióval az is levezethető (3)-ból, hogy $F_{k\mathrm{,}n}$ az összes olyan $a_1^{j_1}{a}_2^{j_2}\text{...}{a}_n^{j_n}$ alakú szorzatok összege, ahol $j_1+j_2+\text{...}+j_n=k-n+1.$ $\left(\text{Így például }{F}_{n\mathrm{,}n}=a_1+a_2+\text{...}+a_n\mathrm{,}{F}_{n+\mathrm{1,}n}=a_1^2+a_2^2+\text{...}+a_n^2+a_1{a}_2+\text{...}+a_1{a}_n+a_2{a}_3+\text{...}+a_2{a}_n+\text{...}+a_{n-1}{a}_n\text{ stb }\mathrm{.}\right)$