Kezdőlap


Feladat:	1337. matematika gyakorlat	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1972/március, 114 - 115. oldal		PDF \| MathML
Témakör(ök):	Számsorozatok, Teljes indukció módszere, Gyakorlat
Hivatkozás(ok):	Feladatok: 1970/december: 1337. matematika gyakorlat

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.

I. megoldás. Az állítás igaz a sorozat első tagjára (az $n = 0$ , $m = 1$ esetén adódó 3-ra), mert az valóban 2-vel kisebb a 2. tagnál (az 5-nél). Tegyük fel, hogy igaz az állítás a sorozat első $k$ tagjára $(k ≧ 1)$ , vagyis az első $k$ tag $P_{k}$ szorzata valóban 2-vel kisebb a sorozat $(k + 1)$ -edik (vagyis az $n = k$ mellett adódó $m = 2^{k}$ kitevőhöz tartozó)

\begin{matrix} a_{k + 1} = 2^{2^{k}} + 1 \end{matrix}

tagjánál. Ekkor az első

(k + 1)

tag szorzata:

\begin{matrix} P_{k + 1} = P_{k} \cdot a_{k + 1} = (a_{k + 1} - 2) a_{k + 1} = (2^{2^{k}} - 1) (2^{2^{k}} + 1) = 2^{2^{k + 1}} - 1, \end{matrix}

ami valóban 2-vel kisebb a sorozat

(k + 2)

-edik tagjánál, vagyis az

m = 2^{k + 1}

kitevőhöz tartozó

(2^{m} + 1)

számnál. Feladatunk állítását ezzel minden

k

természetes számra bebizonyítottuk.

Megjegyzés. Tetszetősnek látszik a következő bizonyítás: szorozzuk meg a

\begin{matrix} P_{k} = (2^{2^{0}} + 1) (2^{2^{1}} + 1) \cdot ... \cdot (2^{2^{k - 1}} + 1) \end{matrix}

szorzatot az 1-gyel egyenlő

(2^{2^{0}} - 1)

számmal. Ekkor az első tényezőt megszorozva

(2^{2^{1}} - 1)

-et kapunk, ezzel a második tényezőt megszorozva

(2^{2^{2}} - 1)

-et kapunk, és így tovább, az utolsó előtti tényezőt megszorozva

(2^{2^{k - 1}} - 1)

-et kapunk, végül ezzel az utolsó tényezőt megszorozva

(2^{2^{k}} - 1)

-et, ami valóban egyenlő

(a_{k + 1} - 2)

-vel. A közben mondott "és így tovább'' kötőszöveg azonban még nem bizonyítja azt, hogy "az utolsó előtti tényezőt megszorozva

(2^{2^{k - 1}} - 1)

-et kapunk''. Ezt az állítást ugyanúgy teljes indukcióval kellene bizonyítanunk, mint ahogy a fenti megoldásban a feladat állítását teljes indukcióval bizonyítottuk: tegyük fel, hogy a

j

-edik tényezőről már beláttuk, hogy az előtte kapott szorzattal beszorozva

(2^{2^{j}} - 1)

-et kapunk, akkor ezzel a most kapott számmal a

(j + 1)

-edik tényezőt beszorozva

\begin{matrix} (2^{2^{j}} - 1) (2^{2^{j}} + 1) = 2^{2^{j + 1}} - 1 \end{matrix}

lesz a szorzat értéke. Természetesen ha már kellő gyakorlatunk van a teljes indukcióval elvégezhető bizonyításokban, akkor ez a lépés elhagyható, nem kell ezt a lépést részletezni, mint ahogy nem szoktuk részletezni a megoldások más, könnyen ellenőrizhető, gondolatban könnyen elvégezhető részét sem. Például nem érezzük szükségét, hogy a fenti szorzások igazolásául az

(a + b) \cdot (a - b) = a^{2} - b^{2}

azonosságra hivatkozzunk.)

II. megoldás. Végezzük el a

\begin{matrix} P_{k} = (2^{2^{0}} + 1) (2^{2^{1}} + 1) \cdot ... \cdot (2^{2^{k - 1}} + 1) \end{matrix}

szorzást a többtagú kifejezések szorzására vonatkozó "minden tagot minden taggal megszorzunk, és a kapott szorzatokat összeadjuk'' szabály szerint. Olyan szorzatokat kapunk, melyek tényezői a fenti kéttagú összegek tagjaiból kerülnek ki, minden egyes kéttagúból vennünk kell valamelyik tagot: vagy a benne szereplő 2-hatványt, vagy az 1-est. E szorzatok mindegyike újra egy 2-hatvány lesz, a kitevő értéke attól függ, hogy az eredeti

\begin{matrix} 2^{0}, 2^{1}, ..., 2^{k - 1} \end{matrix}

kitevők közül melyekhez tartozó 2-hatványok szerepeltek a szorzatban. Egy adott

2^{h}

hatványt annyiszor kapunk meg, ahányféleképpen a

h

szám előállítható a fenti kitevők közül vett valahány kitevő összegeként. Mivel minden,

2^{k}

-nál kisebb számnak egy és csakis egy ilyen előállítása van, az elmondottakból következik, hogy

P_{k}

egyenlő a 2 alap

2^{k}

-nál kisebb kitevőjű hatványainak az összegével:

\begin{matrix} P_{k} = 2^{0} + 2^{1} + 2^{2} + 2^{3} + ... + 2^{2^{k - 1}} = 2^{2^{k}} - 1 = a_{k + 1} - 2. \end{matrix}

Feladatunk állítását ezzel bebizonyítottuk.

Megjegyzés. Ebben a meggondolásban két olyan állítás is van, amelynek a bizonyítását nem részleteztük, és e részletezés ismét teljes indukcióval volna elvégezhető. Mind a kettőnek szemléletes jelentése van a 2 alapú számrendszerben. Az, hogy minden

2^{k}

-nál kisebb szám előállítható különböző (és

k

-nál kisebb kitevőjű) 2-hatványok összegeként, annak felel meg, hogy a 2 alapú számrendszerben a

2^{k}

-nál kisebb számok legfeljebb

k

-jegyűek, és jegyeik között csak 0 vagy 1 szerepel. A második állítás pedig annak felel meg, hogy az a

k

jegyű szám, amelynek minden jegye 1-es, a 2-es számrendszerben 1-gyel kisebb annál a

(k + 1)

-jegyű számnál, amelyiknek első jegye 1-es, a többi 0.