Kezdőlap


Feladat:	F.2837	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Battyányi Péter , Csörnyei Marianna , Egri Ilona , Faragó Gergely , Futó Gábor , Kálmán Tamás , Kórász Tamás , Kotnyek Balázs , Lente Gábor , Miklós György , Molnár-Sáska Gábor , Papolczy Péter , Párniczky Benedek , Pór Attila , Stőhr Lóránt , Szentes Balázs , Tóth Csaba , Ujváry-Menyhárt Zoltán , Wiener Gábor
Füzet:	1991/december, 453 - 454. oldal		PDF \| MathML
Témakör(ök):	Egyenlőtlenségek, Számsorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1991/február: F.2837

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.

Írjuk fel a definíció alapján a sorozat első néhány elemét:

\begin{matrix} a_{0} = 1; & a_{1} = 11; & a_{2} = 31; & a_{3} = 61; \\ a_{4} = 101; & a_{5} = 101; & a_{6} = 281; & a_{7} = 281; \\ a_{8} = 361; & a_{9} = 451; & a_{10} = 451; & a_{11} = 451. \end{matrix}

Láthatjuk, hogy

n = 0

-ra és

n = 1

-re az állításban szereplő becslés éles,

2 ≦ n ≦ 11

esetén viszont nem.
Teljes indukcióval bebizonyítjuk, hogy

2 ≦ n

esetén

a_{n} ≦ 10^{2}

.
Ebből

2 ≦ n ≦ 11

-re következik az állítás.
Állításunk

2 ≦ n ≦ 11

esetén, azaz az előbb felírt elemekre teljesül.
Tegyük fel, hogy

N ≧ 12

olyan szám, hogy

2 ≦ n < N

esetén

a_{n} ≦ 10 n^{2}

teljesül. Megmutatjuk, hogy akkor

a_{N} ≦ 10 N^{2}

, vagyis az állításunk

n = N

esetén is teljesül. A sorozat definíciója szerint

\begin{matrix} a_{N} = 2 a_{[\frac{N}{2}]} + 3 a_{[\frac{N}{3}]} + 6 a_{[\frac{N}{6}]} . \end{matrix}

Mivel

N ≧ 12

, az

[\frac{N}{2}]

[\frac{N}{3}]

és

[\frac{N}{6}]

számok

1

-nél nagyobbak és

N

-nél kisebbek, így az indukciós feltevés alapján

\begin{matrix} a_{[\frac{N}{2}]} ≦ 10 {[\frac{N}{2}]}^{2} ≦ 10 {(\frac{N}{2})}^{2} = \frac{5}{2} N^{2}, \end{matrix}

\begin{matrix} a_{[\frac{N}{3}]} ≦ 10 {[\frac{N}{3}]}^{2} ≦ 10 {(\frac{N}{3})}^{2} = \frac{10}{9} N^{2}, \end{matrix}

\begin{matrix} a_{[\frac{N}{6}]} ≦ 10 {[\frac{N}{6}]}^{2} ≦ 10 {(\frac{N}{6})}^{2} = \frac{5}{18} N^{2} . \end{matrix}

Ezekből a becslésekből

a_{N}

-re azt kapjuk, hogy

\begin{matrix} a_{N} = 2 a_{[\frac{N}{2}]} + 3 a_{[\frac{N}{3}]} + 6 a_{[\frac{N}{6}]} ≦ 2 \cdot \frac{5}{2} N^{2} + 3 \cdot \frac{10}{9} N^{2} + 6 \cdot \frac{5}{18} N^{2} = 10 N^{2} . \end{matrix}

Ezzel az állításunkat ‐ és vele együtt a feladat állítását is ‐ bebizonyítottuk.