Kezdőlap


Feladat:	N.190	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	1999/május, 290 - 292. oldal		PDF \| MathML
Témakör(ök):	Polinomok, Teljes indukció módszere, Algebrai egyenlőtlenségek, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1998/november: N.190

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.

\def

Megoldás. Az állításnak csak

n \geq 100

esetén van értelme (ennél kisebb érték esetén

n - 10 \sqrt[]{n}

negatív), ezért feltehetjük, hogy

n \geq 100

és

\sqrt[]{n} \geq 10

.
Az áttekinthetőség kedvéért a megoldást több segédtétel kimondására és bizonyítására bontjuk szét.
I. segédtétel. Ha az

f (x)

polinom foka kisebb mint

n

, akkor

\begin{matrix} \sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) f (x + k) = 0. \end{matrix}

(1)

Bizonyítás. A segédtételt

f

foka szerinti teljes indukcióval bizonyítjuk. Ha

f

foka

0

, azaz

f

konstans, értéke

c

, akkor tetszőleges pozitív egész

n

esetén

\begin{matrix} \sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) f (x + k) = (\sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k})) c = {(1 - 1)}^{n} c = 0. \end{matrix}

Tegyük fel, hogy (1) igaz

m

-nél kisebb fokú polinomokra. Ebből bebizonyítjuk pontosan

m

-edfokú polinomokra is. Legyen

f

egy pontosan

m

-edfokú polinom. Írjuk fel az indukciós feltevést a

g (x) = f (x) - f (x + 1)

polinomra,

n

helyére

(n - 1)

-et írva. Ezt megtehetjük, mert az

f (x) - f (x + 1)

felírásában az

m

-edfokú tag kiesik, ezért

g

legfeljebb

(n - 1)

-edfokú.

\begin{matrix} \sum_{k = 0}^{n - 1} {(- 1)}^{k} (\binom{n - 1}{k}) g (x + k) = 0. \end{matrix}

Beírva

g

definícióját,

\begin{matrix} \begin{matrix} \sum_{k = 0}^{n - 1} {(- 1)}^{k} (\binom{n - 1}{k}) g (x + k) = \sum_{k = 0}^{n - 1} {(- 1)}^{k} (\binom{n - 1}{k}) (f (x + k) - f (x + k + 1)) = \\ = (\binom{n - 1}{0}) f (x) + \sum_{k = 1}^{n - 1} {(- 1)}^{k} ((\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})) f (x + k) - {(- 1)}^{n - 1} (\binom{n - 1}{n - 1}) f (x + n) = \\ = (\binom{n}{0}) f (x) + \sum_{k = 1}^{n - 1} {(- 1)}^{k} (\binom{n}{k}) f (x + k) + {(- 1)}^{n} (\binom{n}{n}) f (x + n) = \sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) f (x + k) . \end{matrix} \end{matrix}

Ezzel a segédtételt igazoltuk

m

-edfokú polinomokra is.
II. segédtétel. Ha a

p

és

q

polinomok fokszámának összege kisebb, mint

n

, akkor

\begin{matrix} | p (0) | \leq \frac{{max}_{}^{} (| q (1) |, ..., | q (n) |)}{| q (0) |} \sum_{k = 1}^{n} (\binom{n}{k}) | p (k) | . \end{matrix}

(2)

Bizonyítás. Alkalmazzuk az I. segédtételt az

f = p q

polinomra és

x = 0

-ra:

\begin{matrix} \sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) p (k) q (k) = 0. \end{matrix}

Az első tagot felülről becsülve a többivel,

\begin{matrix} | (\binom{n}{0}) p (0) q (0) | = | \sum_{k = 1}^{n} {(- 1)}^{k} (\binom{n}{k}) p (k) q (k) | \leq \sum_{k = 1}^{n} (\binom{n}{k}) | p (k) q (k) |, \end{matrix}

(3)

amiből

\begin{matrix} | p (0) | \leq \frac{1}{| q (0) |} \sum_{k = 1}^{n} (\binom{n}{k}) | p (k) q (k) | \leq \frac{{max}_{}^{} (| q (1) |, ..., | q (n) |)}{| q (0) |} \sum_{k = 1}^{n} (\binom{n}{k}) | p (k) | . \end{matrix}

III. segédtétel. Létezik olyan

q

polinom, amelyre a következők egyszerre teljesülnek:

*	1.A $q$ foka kisebb, mint $10 \sqrt[]{n}$ ;

*	2.A $\| q (1) \|$ , $\| q (2) \|$ , $...$ , $\| q (n) \|$ számok mindegyike legfeljebb $1$ ;

*	3. $q (0) > 10$ .

Bizonyítás. Legyen

m = [10 \sqrt[]{n}] - 1

, és legyen

T_{m}

m

-edik Csebisev-polinom. Ennek a polinomnak nagyon sok nevezetes tulajdonsága van, ezek közül a következőkre lesz szükségünk:

*	a) $T_{m}$ foka pontosan $m$ ;

*	b) Tetszőleges $u$ valós számra $T_{m} (cos u) = cos m u$ és $T_{m} (ch u) = ch m u$ ;

*	c) Ha $\| x \| \leq 1$ , akkor $\| T_{m} (x) \| \leq 1$ .

Válasszuk a

q

polinomot a következőképpen:

\begin{matrix} q (x) = T_{m} (\frac{n + 1 - 2 x}{n - 1}) . \end{matrix}

Mivel ez a polinom is pontosan

m

-edfokú, az 1. tulajdonság teljesül.
Az

x \mapsto \frac{n + 1 - 2 x}{n - 1}

függvény az

1

2

...

n

számokat a

[- 1,1]

intervallumba képezi, ezért a c) tulajdonságból következik a 2. tulajdonság.
A

q (0)

becsléséhez a 2. tulajdonságból tudjuk, hogy

\begin{matrix} q (0) = T_{m} (\frac{n + 1}{n - 1}) = ch (m \cdot ar ch \frac{n + 1}{n - 1}) . \end{matrix}

Mivel tetszőleges

0 < u < \frac{1}{2}

esetén

\begin{matrix} \begin{matrix} ch u = 1 + \sum_{k = 1}^{\infty} \frac{u^{2 k}}{(2 k)!} < 1 + u^{2} \sum_{k = 1}^{\infty} {\frac{1}{2}}^{k} = 1 + u^{2}, \\ ch (1 + \frac{1}{\sqrt[]{n}}) < 1 + \frac{1}{n} < \frac{n + 1}{n - 1}, vagyis ar ch \frac{n + 1}{n - 1} > \frac{1}{\sqrt[]{n}} . \end{matrix} \end{matrix}

Mivel

m > 10 \sqrt[]{n} - 2 > 9 \sqrt[]{n}

, ebből következik, hogy

\begin{matrix} q (0) > ch (9 \sqrt[]{n} \cdot \frac{1}{\sqrt[]{n}}) = ch 9 > 10. \end{matrix}

Ezzel a 3. tulajdonság teljesülését is igazoltuk.
Ha a III. segédtétel

q

polinomját írjuk be a II. segédtételbe, akkor éppen a feladat állítását kapjuk.