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. Az állítást szerinti teljes indukcióval bizonyítjuk. Az esetben az állítás igaz, mert és . Tegyük fel, hogy esetén igaz az állítás, és tegyük fel indirekt, hogy esetén nem, azaz léteznek olyan , , pozitív egészek, amelyekre , de közülük csak legfeljebb hosszúságú monoton növő részsorozat választható ki. Legyen , és jelentse azt, hogy az szám hányszor szerepel az , , számok között. Nyilván , mert ellenkező esetben lenne darab 1-es a sorozatban. Legyen most . Az , , számok mind kisebbek -nél, és közülük az indukciós feltevés szerint kiválasztható hosszúságú, monoton növő részsorozat. Ezekhez hozzávéve darab -et, egy hosszúságú monoton növő sorozatot kapunk; ezért az indirekt feltevés szerint , tehát . Ha összeszámoljuk, hogy az , , sorozatban hány 1-es, 2-es stb. elem szerepel, akkor mindegyik -t egyszer számoljuk, ezért a -ek összege éppen . Ez és az előbbi becslések alapján | | ami ellentmondás.
Megjegyzés. A feladat állítása éles; létezik olyan , , pozitív egész számokból álló sorozat, hogy , és tetszőleges pozitív egészre az , , számok közül nem választható ki hosszúságú monoton növő részsorozat. Legyen , ha : | | Ekkor az , , , , részsorozatok szigorúan monoton fogynak, emiatt egy monoton növő részsorozat mindegyikből legfeljebb egy elemet, összesen legfeljebb elemet tartalmazhat. A megoldás kis módosításával igazolható, hogy ez az egyetlen ilyen példa.
|