Kezdőlap


Cím:	A teljes indukcióra vonatkozó feladatok megoldásai
Füzet:	1950/május, 128 - 135. oldal	PDF \| MathML

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.

1. Mely számtól kezdve lesz

\begin{matrix} π (x) ≦ \frac{x}{3} ? \end{matrix}

Megoldás: Annak megmutatásához, hogy

π (x) ≦ \frac{x}{2}

azt használtuk fel, hogy két egymás után következő szám közül az egyik páros, tehát, ha

2

-nél nagyobb, akkor nem lehet prímszám. Annak megmutatásához, hogy valahonnan kezdve

π (x) ≦ \frac{x}{3}

vegyük igénybe a

3

-mal osztható számokat is. Ha három egymás utáni számot veszünk, ezek egyike osztható

3

-mal és legalább egy páros, de, ha csak három számot vizsgálunk, akkor nem mondhatjuk, hogy ezek kétharmada összetett, mert lehet, hogy a középső osztható

2

-vel és hárommal is, azaz

6

-tal a másik kettő meg prím, mint például

41

42

43

. Jobb lesz azért

2 \cdot 3

, azaz hat számot vennünk. Ezek közül egy mindig osztható

6

-tal, még további kettő lesz páros, és még egy osztható

3

-mal. Így tehát

6

szám közül legfeljebb

2

lehet prímszám, ha az első szám legalább 4 (azaz a számoknak legfeljebb

1 / 3

-a):

\begin{matrix} π (x + 6) ≦ π (x) + 2, ha x > 3. \end{matrix}

Tegyük fel most, hogy létezik egy olyan

x

, melyre a

π (x) ≦ \frac{x}{3}

, akkor előbbi eredményünkből

\begin{matrix} π (x + 6) ≦ π (x) + 2 ≦ \frac{x}{3} + 2 = \frac{x + 6}{3}, \end{matrix}

vagyis, ha a tétel igaz

x

-re, igaz

x + 6

-ra is.

6

egymás utáni számot kell tehát keresnünk, melyekre a tétel igaz, akkor tudjuk, hogy onnan minden

x

-re igaz.

30

az első olyan szám, amire a tétel igaz, mert

π (30) = 10 = \frac{30}{3} \cdot 31

és

32

-re ismét nem igaz.

π (33) = 11 = \frac{33}{3}

π (34) = 11 < \frac{34}{3}

π (35) = 11 < \frac{35}{3}

π (36) = 11 < \frac{36}{3}

π (37) = 12 < \frac{37}{3}

π (38) = 12 < \frac{38}{3}

.
Tehát

π (x) ≦ \frac{x}{3}

, midőn

x ≧ 33

2. Keressétek az

a x + b y = c

elsőfokú határozatlan egyenletnek egész

x

y

megoldását, ha

a

b

c

egész számok.

3. Hogyan lehet az előbbi egyenlet összes megoldásait előállítani? Mi a feltétele annak, hogy legyen ilyen megoldás?

Megoldás: 2. Először is, nyilvánvaló, hogy

c

-nek oszthatónak kell lennie

(a, b) = d

-vel, mert

a

is osztható vele,

b

is, tehát ha

x

és

y

bármilyen egész számok, az

a x + b y

összegből mindig kiemelhető a

d

közös tényező. Azonban ez a feltétel elegendő is. Tudjuk ugyanis, hogy

a

és

b

legnagyobb közös osztója előállítható a következő alakban:

d = (a, b) = a ξ + b η

, ahol

ξ

és

η

valamilyen egész szám. Mivel

c = d c_{1}

, ezt az egyenletet

c_{1}

-gyel szorozva:

\begin{matrix} a ξ c_{1} + b η c_{1} = d c_{1} = c \end{matrix}

és így

c_{1} ξ

és

c_{1} η

kielégítik a megoldandó egyenletet.

3. Feltehetjük, hogy

a

és

b

relatív prímek, mert, ha nem volnának azok, végigoszthatunk legnagyobb közös osztójukkal, lévén evvel

c

is osztható. Legyen

x_{0}

, és

y_{0}

, az egyenletnek megoldása, akkor

a x_{0} + b y_{0} = c

és tegyük fel, hogy

x

és

y

is kiélégítik az egyenletet, azaz

a x + b y = c

. A két egyenlet jobb oldala egyenlő lévén, baloldaluk is egyenlő:

\begin{matrix} a x_{0} + b y_{0} = a x + b y, \end{matrix}

vagyis

\begin{matrix} a (x_{0} - x) = b (y - y_{0}) . \end{matrix}

Mivel

a

és

b

relatív prímek, kell, hogy pl.

(y - y_{0})

osztható legyen

a

-val

(y - y_{0}) = a t

, ebből következik, hogy

x_{0} - x = b t

és így

y = y_{0} + a t

és

x = x_{0} - b t

alakban írhatók az egyenlet összes gyökei. Fordítva bebelyettesítéssel meggyőződhetünk, hogy minden ilyen alakú számpár megoldása az egyenletnek, tehát

x = x_{0} - b t

y = y_{0} + a t

, ahol

t = 0, \pm 1, \pm 2 ...,

az egyenlet összes megoldásait szolgáltatja.

4. Számítsuk ki az

x^{2} + x + 41

kifejezés értékét különböző egész helyeken és bontsuk törzstényezőkre.
Igaz-e, hogy a kifejezés minden egész

x

-re törzsszámot állít elő?

5. Bizonyítsuk be, hogy egy egyváltozós polinom, akárhányad fokú, nem állíthat elő a változó minden egész értékére prímszámot.

Megoldás: 4. Ennek a függvénynek az az érdekessége, hogy igen sok számra, köztük a

0

-tól

40

-ig, és

- 40

-ig terjedőkre prímszámot állít elő. Mégis könnyen belátható, hogy a második kérdésre tagadó a válasz. Például az

x = 41

helyen a függvény értéke

41^{2} + 41 + 41 = 43 \cdot 41

nem prímszám.

5. Hasonlóan találhatunk minden polinomhoz olyan egész helyet, ahol összetett szám az értéke. Jelöljük a polinomot

f (x)

-szel.
Ha

f (x)

-nek nincs állandó tagja, akkor az

x

minden tagból kiemelhető, így a polinom mindig osztható

x

-szel. Az

x

kiemelése után maradó polinom értéke viszont nem lehet minden egész helyen

1

, mert ha

g (x)

egy ilyen polinom volna, akkor a

g (x) - 1 = 0

algebrai egyenletnek végtelen sok gyöke volna, de egy egyenletnek nem lehet több gyöke, mint ahányad fokú.
Ha a polinomnak van állandó tagja, és az nem

1

, ezt jelöljük

c

-vel. A többi tagból kiemelhető

x

, s így a polinom így írható:

f (x) = x g (x) + c

. Így

f (c y) = c [y g (c y) + 1]

. A zárójelben levő polinom értéke pedig nem lehet minden egész

y

-ra

1

.
Ha az állandó tag

1

, akkor először keressünk egy olyan

a

helyet, ahol

f (a)

se nem

0

se nem

1

. Ilyen hely biztosan van, mert az

f (x) = 0

és

f (x) = 1

egyenleteknek összesen is csak véges számú megoldása lehet.

x

helyett

y + a

-t írva és a hatványozásokat elvégezve

y

-nak egy polinomját kapjuk:

g (y) = f (a + y)

. Ennek az állandó tagja ugyanaz, mint a

0

helyen való értéke:

g (0) = f (a)

, ami se nem

0

se nem

1

. Így a

g (y)

polinomra már alkalmazhatjuk az előbbi meggondolást, tehát van egy olyan

y_{0}

hely, ahol

g (y_{0}) = f (y_{0} + a)

összetett szám.

6. Adva vannak a térben egyenesek, melyek páronkint metszik egymást, de semelyik három nem fekszik egy síkban.
Bizonyítsuk be, hogy az összes egyenesek egy ponton mennek keresztül.

Megoldás: A tétel bizonyítása ugyanúgy történhetik, mint a cikkben a hasonló síkbeli hamis bizonyítás, csak most három egyenes esetén is igaz a tétel s így már helyes bizonyítást kapunk.
Két egyenes esetén az állítás a feltételekben már benne foglaltatik. Egy harmadik egyenes nem metszheti az első kettőt azok metszéspontjától különböző pontban, mert akkor benne feküdne azok síkjában. Így három egyenes esetére is igaz a tétel.
Tegyük fel, hogy bebizonyítottuk már a tételt

k

számú és

k - 1

számú egyenes esetére is

(k ≧ 3)

Megmutatjuk, hogy akkor igaz

k + 1

olyan egyenesre is, melyek eleget tesznek a feltételnek. Ha egy egyenest elveszünk a maradó

k

az indukciós feltevés szerint tudjuk, hagy egy ponton megy keresztül. Jelöljük az elvett egyenest

a

-val. Vegyünk el helyette most egy másik

b

egyenest. Ismét

k

egyenes marad. Ezek tehát szintén egy ponton mennek keresztül. Az első ponton átmegy

b

is, a másikon

a

is. Így azt kell még belátni, hogy ez a két pont azonos. Vegyük el most

a

-t is

b

-t is. A maradó

k - 1

egyenesre is igaz a tétel az indukciós feltevés szerint, tehát kell, hogy ezek is egy ponton menjenek keresztül és ez egy meghatározott pont (

k - 1

, tehát legalább

2

különböző egyenesről van szó, ezeknek pedig nem lehet

1

-nél több közös pontjuk). Ezen a ponton kell tehát

a

-nak és

b

-nek is átmennie, azaz mind a

k + 1

egyenesnek.
Mivel két kezdő értékre,

2

-re és

3

-ra a tétel igaz, így most már következik, hogy igaz akárhány egyenesre.

7. Mutassuk meg, hogy

\begin{matrix} \frac{a_{1}}{1 + a_{1}} + \frac{a_{2}}{(1 + a_{1}) (1 + a_{2})} + ... + \\ + \frac{a_{n}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n})} = \\ = 1 - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n}) .} \end{matrix}

I. megoldás: Jelöljük a baloldali összeget

S_{n}

-nel. Teljes indukcióval következőképpen bizonyítható az állítás. Nézzük meg, igaz-e a tétel

n = 1

-re. Ekkor

S_{1} = \frac{a_{1}}{1 + a_{1}}

. A jobboldalon

1 - \frac{1}{1 + a_{1}} = \frac{1 + a_{1} - 1}{1 + a_{1}} = \frac{a_{1}}{1 + a_{1}}

van, tehát

n = 1

-re a tétel igaz.
Tegyük fel most, hogy a tétel igaz valamilyen

n = k

-ra, azaz

\begin{matrix} S_{k} = 1 - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k})} . \end{matrix}

Adjuk mindkét oldalhoz hozzá a

k + 1

-edik tagot:

\begin{matrix} S_{k + 1} = S_{k} + \frac{a_{k + 1}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k}) (1 + a_{k + 1})} = \\ = 1 - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k})} + \\ + \frac{a_{k + 1}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k}) (1 + a_{k + 1})} = \\ = 1 - [\frac{1 + a_{k + 1}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k}) (1 + a_{k + 1})} - \\ - \frac{a_{k + 1}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k}) (1 + a_{k + 1})}] = \\ = 1 - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k}) (1 + a_{k + 1}),} \end{matrix}

és így a tétel igaz

n = (k + 1)

-re is. Ezzel megmutattuk, hogy a tétel igaz minden

n

-re.

II. megoldás: A teljes indukciós megoldás nem mutatja meg azonban, miért igaz a tétel. Ennek okát a következőképen láthatjuk.
A sorozat

k

-adik tagját így lehet felírni:

\begin{matrix} \frac{a_{k}}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k - 1}) (1 + a_{k})} = \\ = \frac{(1 + a_{k}) - 1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k - 1}) (1 + a_{k})} = \\ = \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k - 1})} - \\ - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k - 1}) (1 + a_{k})}, \end{matrix}

és így

\begin{matrix} S_{n} = (1 - \frac{1}{1 + a_{1}}) + (\frac{1}{1 + a_{1}} - \frac{1}{(1 + a_{1}) (1 + a_{2})}) + \\ + (\frac{1}{(1 + a_{1}) (1 + a_{2})} - \frac{1}{(1 + a_{1}) (1 + a_{2}) (1 + a_{3})}) + ... + \\ + (\frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k - 1})} - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k})}) + \\ + (\frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k})} - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{k + 1})}) + \\ + ... + (\frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n - 2})} - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n - 1})}) + \\ + (\frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n - 1})} - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n})}) = \\ = 1 - \frac{1}{(1 + a_{1}) (1 + a_{2}) ... (1 + a_{n})} . \end{matrix}

8. Mutassuk meg hogy:

\begin{matrix} sin α + sin 2 α + ... ... + sin n α = \frac{sin \frac{n α}{2} sin \frac{(n + 1) α}{2}}{sin \frac{α}{2}} . \end{matrix}

I. megoldás: Jelöljük a baloldali összeget

S_{n}

-nel. Ha

n = 1

, a jobboldalon

\begin{matrix} \frac{sin \frac{α}{2} sin α}{sin \frac{α}{2}} = sin α = S_{1} \end{matrix}

áll. Tegyük fel most, hogy a tétel igaz

n = (k - 1)

-re, vagyis

\begin{matrix} S_{k - 1} = \frac{sin \frac{(k - 1) α}{2} sin \frac{k α}{2}}{sin \frac{α}{2}} . \end{matrix}

Adjunk mindkét oldalhoz

sin k α

-t.

\begin{matrix} S_{k} = S_{k - 1} + sin k α = \frac{sin \frac{(k - 1) α}{2} sin \frac{k α}{2}}{sin \frac{α}{2}} + sin 2 \frac{k α}{2} = \\ = \frac{sin \frac{(k - 1) α}{2} sin \frac{k α}{2} + sin \frac{α}{2} \cdot 2 sin \frac{k α}{2} cos \frac{k α}{2}}{sin \frac{α}{2}} = \\ = \frac{sin \frac{k α}{2}}{sin \frac{α}{2}} (sin \frac{(k - 1) α}{2} + 2 sin \frac{α}{2} cos \frac{k α}{2}) = \\ = \frac{sin \frac{k α}{2}}{sin \frac{α}{2}} [sin \frac{(k - 1) α}{2} + (sin \frac{(k + 1) α}{2} - sin \frac{(k - 1) α}{2})] = \\ = \frac{sin \frac{k α}{2} sin \frac{(k + 1)}{2} α}{sin \frac{α}{2}}, \end{matrix}

és így a tétel igaz

n = k

-ra is. Ezzel megmutattuk, hogy a tétel igaz minden

n

-re.

II. megoldás: A jobboldal mutatja, hogy

S_{n} sin \frac{α}{2}

-et lesz célszerű megpróbálni átalakítani:

\begin{matrix} S_{n} sin \frac{α}{2} = sin α sin \frac{α}{2} + sin 2 α sin \frac{α}{2} + ... + sin n α sin \frac{α}{2}, \end{matrix}

\begin{matrix} sin k α sin \frac{α}{2} = \frac{1}{2} (cos \frac{(2 k - 1) α}{2} - cos \frac{(2 k + 1) α}{2}) \end{matrix}

és így

\begin{matrix} S_{n} sin \frac{α}{2} = \frac{1}{2} [(cos \frac{α}{2} - cos \frac{3 α}{2}) + (cos \frac{3 α}{2} - cos \frac{5 α}{2}) + \\ + (cos \frac{5 α}{2} - cos \frac{7 α}{2}) + ... + (cos \frac{(2 n - 3) α}{2} - cos \frac{(2 n - 1) α}{2}) + \\ + (cos \frac{(2 n - 1) α}{2} - cos \frac{(2 n + 1) α}{2})] = \\ = \frac{1}{2} (cos \frac{α}{2} - cos \frac{(2 n + 1) α}{2}) = sin \frac{(n + 1) α}{2} sin \frac{n α}{2}, \end{matrix}

vagyis

\begin{matrix} S_{n} = \frac{sin \frac{(n + 1) α}{2} sin \frac{n α}{2}}{sin \frac{α}{2}} . \end{matrix}