Kezdőlap


Feladat:	N.149	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Juhász András , Lippner Gábor , Lukács László
Füzet:	1998/március, 163 - 165. oldal		PDF \| MathML
Témakör(ök):	Rekurzív eljárások, Számsorozatok, Polinomok, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/október: N.149

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.

Megmutatjuk, hogy $a_{n}$ nem más, mint az ${(1 + x + x^{2})}^{n}$ polinomban $x^{n}$ együtthatója. Jelöljük egyelőre $c_{n}$ -nel az $x^{n}$ együtthatóját az ${(1 + x + x^{2})}^{n}$ polinomban. Azt könnyű ellenőrizni, hogy $c_{0} = a_{0} = 1$ és $c_{1} = a_{1} = 1$ . Mivel

\begin{matrix} {(1 + x + x^{2})}^{n} = x^{n} {(1 + x + \frac{1}{x})}^{n} = x^{n} \sum_{k = 0}^{n} n ch o o s e k {(x + \frac{1}{x})}^{k}, \end{matrix}

ebből az alakból kiolvasható, hogy

\begin{matrix} c_{n} = \sum_{0 \leq k \leq \frac{n}{2}}^{} n ch o o s e 2 k 2 k ch o o s e k = \sum_{0 \leq k \leq \frac{n}{2}}^{} \frac{n!}{k!^{2} (n - 2 k)!} . \end{matrix}

(1)

Az (1) azonosság egyszerű átrendezéseiből kapjuk, hogy

\begin{matrix} \begin{matrix} c_{n + 1} = & \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot n (n + 1), \\ c_{n} = & \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot n (n - 2 k + 1), \\ c_{n - 1} = & \sum_{0 \leq k \leq \frac{n - 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k - 1)!} = \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot (n - 2 k) (n - 2 k + 1), \\ c_{n - 1} = & \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{(k - 1)!^{2} (n - 2 k + 1)!} = \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot k^{2} . \end{matrix} \end{matrix}

Ezek alapján

\begin{matrix} \begin{matrix} (2 n + 1) c_{n} + 3 n c_{n - 1} = (2 n + 1) c_{n} + 4 n c_{n - 1} - n c_{n - 1} = \\ = \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot ((2 n + 1) n (n - 2 k + 1) + 4 n k^{2} - n (n - 2 k) (n - 2 k + 1)) = \\ = \sum_{0 \leq k \leq \frac{n + 1}{2}}^{} \frac{(n - 1)!}{k!^{2} (n - 2 k + 1)!} \cdot n {(n + 1)}^{2} = (n + 1) c_{n + 1}, \end{matrix} \end{matrix}

vagyis az

(a_{n})

és

(c_{n})

sorozatokra ugyanaz a rekurzió teljesül.

Megjegyzések. 1. Egy polinom együtthatóit komplex függvénytani eszközökkel is lehet kezelni. Például az

{(x^{2} + x + 1)}^{n}

polinomban

x^{n}

együtthatóját felírhatjuk a következő alakban:

\begin{matrix} c_{n} = \frac{1}{2 π} \int_{- π}^{π} {(e^{2 i t} + e^{i t} + 1)}^{n} e^{- i n t} d t . \end{matrix}

Ebből a rekurzió parciális integrálással nyerhető. (A feladat innen származik.)
2. Lippner Gábor és Lukács László az

F (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}

generátorfüggvény vizsgálatával egy érdekes azonosságot fedezett fel:

\begin{matrix} a_{0} a_{n} + a_{1} a_{n - 1} + ... + a_{n - 1} a_{1} + a_{n} a_{0} = \frac{3^{n + 1} + {(- 1)}^{n}}{4} . \end{matrix}

(2)

Nem nehéz végiggondolni, hogy

F

definíciója

| x | < \frac{1}{3}

esetén értelmes, és ebben az intervallumban teljesül rá a

\begin{matrix} \begin{matrix} (3 x^{2} + 2 x - 1) F' (x) + (3 x + 1) F (x) = 0; F (0) = 1 \end{matrix} \end{matrix}

homogén lineáris differenciálegyenlet. Ezt megoldva

F (x) = \frac{1}{\sqrt[]{(1 - 3 x) (1 + x)}}

\begin{matrix} \begin{matrix} F^{2} (x) = \frac{\frac{3}{4}}{1 - 3 x} + \frac{\frac{1}{4}}{1 + x} = \frac{3}{4} \sum_{n = 0}^{\infty} {(3 x)}^{n} + \frac{1}{4} \sum_{n = 0}^{\infty} {(- x)}^{n} = \sum_{n = 0}^{\infty} \frac{3^{n + 1} + {(- 1)}^{n}}{4} x^{n} . \end{matrix} \end{matrix}

Másfelől

\begin{matrix} \begin{matrix} F^{2} (x) = {(\sum_{n = 0}^{\infty} a_{n} x^{n})}^{2} = \sum_{n = 0}^{\infty} (a_{0} a_{n} + ... + a_{n} a_{0}) x^{n}, \end{matrix} \end{matrix}

és a függvény az együtthatókat egyértelműen meghatározza, ebből (2) következik.
Természetesen (2) bizonyításához nincs szükség analitikus eszközökre, teljes indukcióval is igazolható.
A (2) azonosságból a feladat állítása viszonylag egyszerűen következik.