Feladat:	B.4330	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ágoston Péter ,  Baráti László ,  Beleznay Soma ,  Bősze Zsuzsanna ,  Bunth Gergely ,  Czipó Bence ,  Énekes Péter ,  Halász Dániel ,  Homonnay Bálint ,  Kabos Eszter ,  Kiss Robin ,  Kusz Ágnes ,  Lenger Dániel ,  Ódor Gergely ,  Sándor Áron Endre ,  Strenner Péter ,  Szabó Attila ,  Tekeli Tamás ,  Tran Trong Hoang Tuan ,  Vajk Dóra ,  Viharos Andor ,  Vuchetich Bálint ,  Weisz Gellért ,  Zelena Réka
Füzet:	2012/szeptember, 350 - 351. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Rekurzív sorozatok, Teljes indukció módszere, Polinomok
Hivatkozás(ok):	Feladatok: 2011/január: B.4330

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.   Megoldás. Használjuk az $\begin{array}{c}{\displaystyle S_k=x^k-y^k}\end{array}$ jelölést minden $k$ pozitív egészre; legyen továbbá $x+y=a$ és $xy=b$. Az ismert azonosság szerint $\begin{array}{c}{\displaystyle \sum _{k=0}^{20}{x}^{20-k}{y}^k=\frac{S_{21}}{x-y}=\frac{S_{21}}{S_1}\mathrm{.}}\end{array}$ Ha $n>1$, akkor $\begin{array}{c}{\displaystyle S_{n+1}=x^{n+1}-y^{n+1}=\left(x^n-y^n\right)\left(x+y\right)-\left(x^{n}y-x{y}^n\right)=a{S}_n-b{S}_{n-1}\mathrm{.}}\end{array}$ Ezt alkalmazva $n=\mathrm{1,2,}\text{...}\mathrm{,6}$-ra: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle S_1}& {\displaystyle =x-y\mathrm{,}}\hfill \\ \hfill {\displaystyle S_2}& {\displaystyle =a\left(x-y\right)=a{S}_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_3}& {\displaystyle =a^2\left(x-y\right)-b\left(x-y\right)=\left(a^2-b\right)S_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_4}& {\displaystyle =a\left(a^2-b\right)S_1-ba{S}_1=\left(a^3-2ab\right)S_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_5}& {\displaystyle =a\left(a^3-2ab\right)S_1-b\left(a^2-b\right)S_1=\left(a^4-3a^{2}b+b^2\right)S_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_6}& {\displaystyle =a\left(a^4-3a^{2}b+b^2\right)S_1-b\left(a^3-2ab\right)S_1=\left(a^5-4a^{3}b+3a{b}^2\right)S_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_7}& {\displaystyle =a\left(a^5-4a^{3}b+3a{b}^2\right)S_1-b\left(a^4-3a^{2}b+b^2\right)S_1=\left(a^6-5a^{4}b+6a^2{b}^2-b^3\right)S_1\mathrm{.}}\hfill \end{array}}$ Végül $\begin{array}{c}{\displaystyle S_{21}=x^{21}-y^{21}={\left(x^7\right)}^3-{\left(y^7\right)}^3=\left(x^7-y^7\right)\left({\left(x^7\right)}^2+x^7{y}^7+{\left(y^7\right)}^2\right)=S_7\left(S_7^2+3b^7\right)}\end{array}$ alapján ${\displaystyle \begin{array}{cc}\hfill {\displaystyle \frac{S_{21}}{x-y}}& {\displaystyle ={\left(a^6-5a^{4}b+6a^2{b}^2-b^3\right)}^3{S}_1^2+3b^7\left(a^6-5a^{4}b+6a^2{b}^2-b^3\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle ={\left(a^6-5a^{4}b+6a^2{b}^2-b^3\right)}^3\left(a^2-4b\right)+3b^7\left(a^6-5a^{4}b+6a^2{b}^2-b^3\right)\mathrm{.}}\hfill \end{array}}$ Így a keresett polinom ${\displaystyle \begin{array}{cc}\hfill {\displaystyle p\left(z\mathrm{,}t\right)}& {\displaystyle ={\left(z^6-5z^{4}t+6z^2{t}^2-t^3\right)}^3\left(z^2-4t\right)+3t^7\left(z^6-5z^{4}t+6z^2{t}^2-t^3\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =z^{20}-19z^{18}t+153z^{16}{t}^2-680z^{14}{t}^3+1820z^{12}{t}^4-3003z^{10}{t}^5+3003z^8{t}^6-}\hfill \\ \hfill {\displaystyle }& {\displaystyle -1716z^6{t}^7+495z^4{t}^8-55z^2{t}^9+t^{10}\mathrm{.}}\hfill \end{array}}$   Megjegyzés. Általában, a $\begin{array}{c}{\displaystyle p_n\left(x+y\mathrm{,}xy\right)=\sum _{k=0}^n{x}^{n-k}{y}^k}\end{array}$ követelményt kielégítő $p_n=p_n\left(z\mathrm{,}t\right)$ polinomokra a megoldásban alkalmazott $S_{n+1}=a{S}_n-b{S}_{n-1}$ rekurzió megfelelőjeként teljesülő $\begin{array}{c}{\displaystyle p_{n+1}\left(z\mathrm{,}t\right)=z{p}_n\left(z\mathrm{,}t\right)-t{p}_{n-1}\left(z\mathrm{,}t\right)}\end{array}$ rekurzió segítségével, az $n$-re vonatkozó indukcióval belátható, hogy $\begin{array}{c}{\displaystyle p_n\left(z\mathrm{,}t\right)=\sum _{i=0}^{\left[n/2\right]}{\left(-1\right)}^i\left(\genfrac{}{}{0ex}{}{n-i}{i}\right)z^{n-2i}{t}^i\mathrm{.}}\end{array}$