A teljes indukció elvének és lépéseinek precíz alkalmazása
A teljes indukció egyike a leghatékonyabb bizonyítási módszereknek a diszkrét matematikában és az algebrában. Lényege a dominó-elv: ha az állítás igaz egy kezdőértékre (alapeset), és minden elemről öröklődik a következőre (indukciós lépés), akkor minden természetes számra teljesül. Ebben a modulban az emelt érettségin tipikusan előforduló komplex oszthatósági feladatokat, algebrai azonosságokat és egyenlőtlenségeket vizsgálunk meg részletes bizonyításokkal.
1
Bizonyítsa be a teljes indukció elvének alkalmazásával, hogy minden $n$ pozitív egész szám esetén az első $n$ darab páratlan szám összege $n^2$.
1. Alapeset: Vizsgáljuk meg az állítást $n=1$ esetén. Az első páratlan szám az 1, és $1^2 = 1$, tehát az állítás igaz.
2. Indukciós feltevés: Tegyük fel, hogy valamilyen tetszőleges $n=k$ pozitív egész számra az állítás igaz, azaz:
$$ 1 + 3 + 5 + \dots + (2k-1) = k^2 $$ 3. Indukciós lépés: Bizonyítsuk be az állítást $n=k+1$ esetén. Ekkor az összeghez hozzáadjuk a következő, $(k+1)$-edik páratlan számot, ami a $2(k+1)-1 = 2k+1$.
$$ \left[ 1 + 3 + \dots + (2k-1) \right] + (2k+1) = k^2 + 2k + 1 $$
A jobb oldalon a nevezetes azonosság alapján $(k+1)^2$ áll elő, így beláttuk az állítást $n=k+1$-re is.
2
Igazolja, hogy minden $n$ pozitív egész számra teljesül a következő azonosság: $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$.
Alapeset: Ha $n=1$, akkor az összeg bal oldala $1^2=1$. A jobb oldal: $\frac{1(1+1)(2\cdot 1+1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = 1$. Az állítás igaz.
Indukciós feltevés: Tegyük fel, hogy $n=k$-ra igaz: $\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$.
Indukciós lépés: Vizsgáljuk $n=k+1$-re:
$$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 $$
Kiemeljük a $(k+1)$ tényezőt, és közös nevezőre hozunk:
$$ (k+1) \left[ \frac{k(2k+1)}{6} + \frac{6(k+1)}{6} \right] = \frac{k+1}{6} \left( 2k^2 + k + 6k + 6 \right) $$
$$ = \frac{k+1}{6} (2k^2 + 7k + 6) $$
A másodfokú kifejezés gyöktényezős alakja: $(k+2)(2k+3)$. Visszaírva:
$$ \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} $$
Ami pontosan az eredeti formula $n=k+1$-re.
3
Bizonyítsa be, hogy minden természetes $n \ge 1$ esetén $\sum_{k=1}^n k^3 = \left( \frac{n(n+1)}{2} \right)^2$.
Alapeset ($n=1$): Bal oldal $1^3 = 1$, jobb oldal $\left(\frac{1 \cdot 2}{2}\right)^2 = 1^2 = 1$. Igaz.
Indukciós feltevés: Tegyük fel, hogy $n$-re igaz az állítás.
Indukciós lépés: Adjuk hozzá az egyenlet mindkét oldalához az $(n+1)^3$-t:
$$ \sum_{k=1}^{n+1} k^3 = \frac{n^2(n+1)^2}{4} + (n+1)^3 $$
Kiemelve az $(n+1)^2$-t:
$$ = (n+1)^2 \left[ \frac{n^2}{4} + (n+1) \right] = (n+1)^2 \left[ \frac{n^2 + 4n + 4}{4} \right] $$
Mivel $n^2+4n+4 = (n+2)^2$, ez felírható úgy, hogy $\left( \frac{(n+1)(n+2)}{2} \right)^2$, ami bizonyítja a formulát $n+1$-re.
4
Lássa be, hogy a $3^{2n} - 1$ kifejezés minden $n$ pozitív egész szám esetén osztható 8-cal.
Alapeset: Ha $n=1$, akkor $3^2 - 1 = 9 - 1 = 8$, ami triviálisan osztható 8-cal.
Indukciós feltevés: Tegyük fel, hogy $n=k$-ra az állítás igaz, tehát van olyan $m$ egész szám, hogy $3^{2k} - 1 = 8m$. Ebből adódik, hogy $3^{2k} = 8m + 1$.
Indukciós lépés: Nézzük meg a kifejezést $n=k+1$-re:
$$ 3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 3^2 \cdot 3^{2k} - 1 = 9 \cdot 3^{2k} - 1 $$
A feltevés alapján helyettesítsük be a $3^{2k}$ értékét:
$$ 9 \cdot (8m + 1) - 1 = 72m + 9 - 1 = 72m + 8 = 8(9m + 1) $$
Mivel a kifejezést sikerült $8 \cdot \text{egész}$ alakban felírni, ezért $n=k+1$ esetén is osztható 8-cal.
5
Igazolja, hogy az $5^n + 2 \cdot 3^{n-1} + 1$ kifejezés osztható 8-cal minden $n$ pozitív egész számra.
Indukciós feltevés: Tegyük fel, hogy $n=k$-ra $5^k + 2 \cdot 3^{k-1} + 1 = 8A$, ahol $A$ egész. Ebből $5^k = 8A - 2 \cdot 3^{k-1} - 1$.
Indukciós lépés: Írjuk fel $n=k+1$-re:
$$ 5^{k+1} + 2 \cdot 3^k + 1 = 5 \cdot 5^k + 2 \cdot 3^k + 1 $$
Behelyettesítve $5^k$ feltevésből nyert értékét:
$$ 5(8A - 2 \cdot 3^{k-1} - 1) + 2 \cdot 3^k + 1 = 40A - 10 \cdot 3^{k-1} - 5 + 2 \cdot 3^k + 1 $$
A $2 \cdot 3^k$ felírható $6 \cdot 3^{k-1}$ formában:
$$ 40A - 10 \cdot 3^{k-1} + 6 \cdot 3^{k-1} - 4 = 40A - 4 \cdot 3^{k-1} - 4 $$
Kiemelünk 4-et: $4(10A - 3^{k-1} - 1)$. Most be kell látnunk, hogy a zárójeles kifejezés páros. $3^{k-1}$ mindenképpen páratlan, így $3^{k-1} + 1$ páros. A $10A$ is páros. Páros számok különbsége páros, tehát $10A - 3^{k-1} - 1 = 2B$. Így a teljes kifejezés $4 \cdot 2B = 8B$, ami osztható 8-cal.
6
Bizonyítsa be, hogy $n^3 + 2n$ osztható 3-mal, ha $n$ tetszőleges pozitív egész szám.
Alapeset: $n=1$ esetén $1^3 + 2 \cdot 1 = 3$, ami osztható 3-mal.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k$ esetén $k^3 + 2k = 3M$, ahol $M$ egész.
Indukciós lépés: $n=k+1$-re:
$$ (k+1)^3 + 2(k+1) = (k^3 + 3k^2 + 3k + 1) + 2k + 2 $$
Rendezzük át a tagokat úgy, hogy megjelenjen a feltevésben szereplő kifejezés:
$$ (k^3 + 2k) + 3k^2 + 3k + 3 $$
Az első zárójel értéke a feltevés miatt $3M$. A többi tagból pedig kiemelhetünk 3-at:
$$ 3M + 3(k^2 + k + 1) = 3(M + k^2 + k + 1) $$
Mivel a kifejezés a 3 többszöröse, az állítást igazoltuk.
7
Lássa be, hogy a $4^n + 15n - 1$ kifejezés minden $n \ge 1$ egész szám esetén osztható 9-cel.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k$-ra $4^k + 15k - 1 = 9m$. Ebből $4^k = 9m - 15k + 1$.
Indukciós lépés: Vizsgáljuk $n=k+1$-re:
$$ 4^{k+1} + 15(k+1) - 1 = 4 \cdot 4^k + 15k + 14 $$
Helyettesítsük be $4^k$-t a feltevésből:
$$ 4(9m - 15k + 1) + 15k + 14 = 36m - 60k + 4 + 15k + 14 = 36m - 45k + 18 $$
Minden tag osztható 9-cel: $9(4m - 5k + 2)$. Ezzel beláttuk az állítást $k+1$-re is.
8
Igazolja, hogy $7^n - 1$ osztható 6-tal, ha $n$ pozitív egész szám.
Alapeset: $n=1$ esetén $7^1 - 1 = 6$, ami osztható 6-tal.
Indukciós feltevés: Tegyük fel $n=k$-ra, hogy $7^k - 1 = 6m$, azaz $7^k = 6m + 1$.
Indukciós lépés: Helyettesítsünk $n=k+1$-et:
$$ 7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1) $$
Mivel $7m + 1$ egész szám, a kifejezés mindig 6 többszöröse.
9
Bizonyítsa be, hogy $2^n > n^2$ teljesül minden $n \ge 5$ egész számra.
Alapeset ($n=5$): $2^5 = 32$, és $5^2 = 25$. Mivel $32 > 25$, az alapeset teljesül.
Indukciós feltevés: Tegyük fel, hogy egy $k \ge 5$ egészre igaz, hogy $2^k > k^2$.
Indukciós lépés: Be kell látnunk, hogy $2^{k+1} > (k+1)^2$.
$$ 2^{k+1} = 2 \cdot 2^k > 2 \cdot k^2 = k^2 + k^2 $$
Tudjuk, hogy be kell bizonyítani: $k^2 + k^2 > (k+1)^2 = k^2 + 2k + 1$.
Ezt úgy érhetjük el, ha megmutatjuk, hogy $k^2 > 2k + 1$ minden $k \ge 5$ esetén.
Osszuk el $k$-val (mivel $k>0$): $k > 2 + \frac{1}{k}$.
Mivel $k \ge 5$, a jobb oldal legfeljebb $2.2$, így $5 > 2.2$ egyértelműen teljesül.
Tehát $2^{k+1} > k^2 + k^2 > k^2 + 2k + 1 = (k+1)^2$.
10
Lássa be a Bernoulli-egyenlőtlenséget, miszerint $(1+x)^n \ge 1+nx$, ahol $n$ pozitív egész szám, $x$ pedig -1-nél nagyobb valós szám.
Alapeset: Ha $n=1$, az egyenlőtlenség $(1+x)^1 \ge 1+1 \cdot x$, ami valójában egyenlőség, tehát igaz.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k \ge 1$ egészre igaz: $(1+x)^k \ge 1+kx$.
Indukciós lépés: Szorozzuk meg a feltevés mindkét oldalát $(1+x)$-szel. Mivel a feltétel szerint $x > -1$, ezért $1+x > 0$, így a relációs jel iránya nem változik:
$$ (1+x)^{k+1} \ge (1+kx)(1+x) $$
Bontsuk fel a jobb oldalt:
$$ (1+kx)(1+x) = 1 + x + kx + kx^2 = 1 + (k+1)x + kx^2 $$
Mivel $k \ge 1$ és $x^2 \ge 0$, a $kx^2$ tag biztosan nem negatív. Ha ezt a tagot elhagyjuk, az érték csökken (vagy változatlan marad, ha $x=0$), így:
$$ 1 + (k+1)x + kx^2 \ge 1 + (k+1)x $$
Ezzel a $(1+x)^{k+1} \ge 1 + (k+1)x$ egyenlőtlenséget beláttuk.
11
Igazolja a mértani sorozat összegképletét teljes indukcióval, azaz lássa be, hogy $\sum_{k=0}^{n-1} q^k = \frac{q^n-1}{q-1}$, ha $q \neq 1$ és $n \ge 1$ egész szám.
Alapeset: $n=1$ esetén a bal oldalon egyetlen tag van, $k=0$-ra: $q^0 = 1$. A jobb oldal: $\frac{q^1-1}{q-1} = 1$. Megegyeznek.
Indukciós feltevés: Tegyük fel, hogy valamilyen $n=m$ esetén az összeg $\frac{q^m-1}{q-1}$.
Indukciós lépés: Adjuk hozzá mindkét oldalhoz az $m$-edik tagot ($q^m$):
$$ \sum_{k=0}^{m} q^k = \frac{q^m-1}{q-1} + q^m = \frac{q^m-1 + q^m(q-1)}{q-1} $$
Bontsuk fel a számlálót:
$$ \frac{q^m - 1 + q^{m+1} - q^m}{q-1} = \frac{q^{m+1} - 1}{q-1} $$
Ami pontosan az állítás $n=m+1$ esetre.
12
Egy sorozatot így definiálunk: $a_1 = 2$, és $a_{n+1} = 3a_n - 1$. Bizonyítsa be, hogy $a_n = \frac{3^n + 1}{2}$ minden pozitív egész $n$-re.
Alapeset: Ha $n=1$, a képlet szerint $a_1 = \frac{3^1 + 1}{2} = \frac{4}{2} = 2$, ami megegyezik a definícióval.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k$ indexre az $a_k$ tag képlete $a_k = \frac{3^k + 1}{2}$.
Indukciós lépés: Számítsuk ki $a_{k+1}$ értékét a rekurzív definíció és az indukciós feltevés felhasználásával:
$$ a_{k+1} = 3a_k - 1 = 3 \left( \frac{3^k + 1}{2} \right) - 1 = \frac{3^{k+1} + 3}{2} - \frac{2}{2} = \frac{3^{k+1} + 1}{2} $$
A kapott eredmény alátámasztja a képlet helyességét a $k+1$ indexre is.
13
Bizonyítsa be, hogy a $11^{n+1} + 12^{2n-1}$ kifejezés osztható 133-mal minden pozitív egész $n$ esetén.
Alapeset: $n=1$ esetén a kifejezés $11^2 + 12^1 = 121 + 12 = 133$, ami triviálisan osztható 133-mal.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k$-ra $11^{k+1} + 12^{2k-1} = 133A$.
Indukciós lépés: Vizsgáljuk $n=k+1$-re a kifejezést:
$$ 11^{k+2} + 12^{2(k+1)-1} = 11 \cdot 11^{k+1} + 12^{2k+1} = 11 \cdot 11^{k+1} + 144 \cdot 12^{2k-1} $$
A $144$-et bontsuk fel $11 + 133$ alakra:
$$ = 11 \cdot 11^{k+1} + (11 + 133) \cdot 12^{2k-1} = 11(11^{k+1} + 12^{2k-1}) + 133 \cdot 12^{2k-1} $$
A zárójelben az indukciós feltevésünk áll, aminek értéke $133A$, így:
$$ 11(133A) + 133 \cdot 12^{2k-1} = 133(11A + 12^{2k-1}) $$
Mivel $11A + 12^{2k-1}$ egész szám, a szorzat biztosan osztható 133-mal.
14
Lássa be, hogy $\sum_{k=1}^n k \cdot k! = (n+1)! - 1$ teljesül minden pozitív egész $n$ számra.
Alapeset: $n=1$ esetén a bal oldal $1 \cdot 1! = 1$. A jobb oldal $(1+1)! - 1 = 2! - 1 = 1$. Az egyenlőség fennáll.
Indukciós feltevés: Tegyük fel, hogy $m$-re igaz az állítás: $\sum_{k=1}^m k \cdot k! = (m+1)! - 1$.
Indukciós lépés: Vizsgáljuk $n=m+1$ esetét:
$$ \sum_{k=1}^{m+1} k \cdot k! = (m+1)! - 1 + (m+1) \cdot (m+1)! $$
Vonjuk össze az azonos faktoriális kifejezéseket:
$$ (m+1)! \left[ 1 + (m+1) \right] - 1 = (m+1)! \cdot (m+2) - 1 $$
A faktoriális definíciója szerint $(m+1)! \cdot (m+2) = (m+2)!$, így a végeredmény:
$$ (m+2)! - 1 $$
Ami pontosan az eredeti formula $(m+1)$-re alkalmazva.
15
Bizonyítsa be, hogy $\prod_{k=2}^n \left(1 - \frac{1}{k^2}\right) = \frac{n+1}{2n}$, ha $n \ge 2$ egész szám.
Alapeset ($n=2$): A szorzat egyetlen tényezőből áll: $1 - \frac{1}{2^2} = 1 - \frac{1}{4} = \frac{3}{4}$. A képlet szerint: $\frac{2+1}{2 \cdot 2} = \frac{3}{4}$. Az alapeset igaz.
Indukciós feltevés: Tegyük fel, hogy valamilyen $k \ge 2$ egészre $\prod_{i=2}^k \left(1 - \frac{1}{i^2}\right) = \frac{k+1}{2k}$.
Indukciós lépés: Szorozzuk be a feltevés mindkét oldalát az $(k+1)$-edik tényezővel:
$$ \prod_{i=2}^{k+1} \left(1 - \frac{1}{i^2}\right) = \frac{k+1}{2k} \cdot \left(1 - \frac{1}{(k+1)^2}\right) $$
Hozzuk közös nevezőre a zárójelen belüli kifejezést:
$$ = \frac{k+1}{2k} \cdot \frac{(k+1)^2 - 1}{(k+1)^2} = \frac{k+1}{2k} \cdot \frac{k^2 + 2k}{(k+1)^2} $$
Egyszerűsítsünk $(k+1)$-gyel:
$$ = \frac{k^2 + 2k}{2k(k+1)} = \frac{k(k+2)}{2k(k+1)} $$
Tovább egyszerűsítve a $k$-val (mivel $k>0$):
$$ = \frac{k+2}{2(k+1)} $$
Ami pont a képlet $n=k+1$-re felírt alakja.
16
Legyen $F_n$ a Fibonacci-sorozat $n$-edik tagja ($F_1=1, F_2=1, F_{n+2}=F_{n+1}+F_n$). Lássa be, hogy $\sum_{i=1}^n F_i = F_{n+2} - 1$ minden pozitív egész $n$-re.
Alapeset ($n=1$): A bal oldal $F_1 = 1$. A jobb oldal $F_3 - 1 = (F_2 + F_1) - 1 = (1+1) - 1 = 1$. Igaz.
Indukciós feltevés: Tegyük fel, hogy $k$-ra $\sum_{i=1}^k F_i = F_{k+2} - 1$.
Indukciós lépés: Adjuk hozzá az összeghez $F_{k+1}$-et:
$$ \sum_{i=1}^{k+1} F_i = (F_{k+2} - 1) + F_{k+1} = (F_{k+2} + F_{k+1}) - 1 $$
A Fibonacci-szabály definíciója szerint $F_{k+2} + F_{k+1} = F_{k+3}$, így a kifejezés egyenlő $F_{k+3} - 1$-gyel, ami az állítás $n=k+1$-re vonatkozó alakja.
17
Igazolja, hogy a $2^{2n-1} + 3^{2n-1}$ kifejezés osztható 5-tel minden $n \ge 1$ egész szám esetén.
Alapeset: Ha $n=1$, $2^1 + 3^1 = 5$, ami osztható 5-tel.
Indukciós feltevés: Tegyük fel, hogy $k$-ra $2^{2k-1} + 3^{2k-1} = 5m$. Ebből $2^{2k-1} = 5m - 3^{2k-1}$.
Indukciós lépés: Írjuk fel a kifejezést $n=k+1$-re:
$$ 2^{2(k+1)-1} + 3^{2(k+1)-1} = 2^{2k+1} + 3^{2k+1} = 4 \cdot 2^{2k-1} + 9 \cdot 3^{2k-1} $$
Helyettesítsük be $2^{2k-1}$ értékét a feltevésből:
$$ 4(5m - 3^{2k-1}) + 9 \cdot 3^{2k-1} = 20m - 4 \cdot 3^{2k-1} + 9 \cdot 3^{2k-1} = 20m + 5 \cdot 3^{2k-1} $$
Kiemeljük az 5-öt: $5(4m + 3^{2k-1})$. Mivel a zárójeles kifejezés egész szám, a teljes érték 5 többszöröse.
18
Bizonyítsa be, hogy $\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \dots + \frac{1}{\sqrt{n}} > \sqrt{n}$ teljesül minden $n \ge 2$ egész számra.
Alapeset ($n=2$): $1 + \frac{1}{\sqrt{2}} > \sqrt{2}$. Szorozzuk meg $\sqrt{2}$-vel a bal oldalt is: $\sqrt{2} + 1 > 2$, ami igaz ($1.41 + 1 > 2$).
Indukciós feltevés: Tegyük fel, hogy valamilyen $k \ge 2$ esetén:
$$ \sum_{i=1}^k \frac{1}{\sqrt{i}} > \sqrt{k} $$ Indukciós lépés: Vizsgáljuk $n=k+1$-et:
$$ \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}} > \sqrt{k} + \frac{1}{\sqrt{k+1}} $$
Meg kell mutatnunk, hogy $\sqrt{k} + \frac{1}{\sqrt{k+1}} > \sqrt{k+1}$.
Rendezzük ezt az egyenlőtlenséget (vonjunk ki $\sqrt{k}$-t):
$$ \frac{1}{\sqrt{k+1}} > \sqrt{k+1} - \sqrt{k} $$
Gyöktelenítsük a jobb oldalt (szorozzuk be a konjugáltjával, $(\sqrt{k+1}+\sqrt{k})$ értékkel):
$$ \sqrt{k+1} - \sqrt{k} = \frac{(k+1) - k}{\sqrt{k+1} + \sqrt{k}} = \frac{1}{\sqrt{k+1} + \sqrt{k}} $$
Mivel a nevezőben $\sqrt{k+1} + \sqrt{k} > \sqrt{k+1}$ (hiszen $k \ge 1$), a tört értéke valóban kisebb, mint $\frac{1}{\sqrt{k+1}}$. Az egyenlőtlenséget igazoltuk.
19
Lássa be, hogy $\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$ minden pozitív egész $n$ esetén.
Alapeset ($n=1$): Bal oldal: $\frac{1}{1(2)} = \frac{1}{2}$. Jobb oldal: $\frac{1}{1+1} = \frac{1}{2}$. Az egyenlőség fennáll.
Indukciós feltevés: Tegyük fel, hogy valamilyen $m$ pozitív egészre $\sum_{k=1}^m \frac{1}{k(k+1)} = \frac{m}{m+1}$.
Indukciós lépés: Adjunk hozzá az összeghez a soron következő, $m+1$-edik tagot:
$$ \sum_{k=1}^{m+1} \frac{1}{k(k+1)} = \frac{m}{m+1} + \frac{1}{(m+1)(m+2)} $$
Hozzuk közös nevezőre a jobb oldalt:
$$ = \frac{m(m+2) + 1}{(m+1)(m+2)} = \frac{m^2 + 2m + 1}{(m+1)(m+2)} $$
A számláló $(m+1)^2$ alakba írható:
$$ \frac{(m+1)^2}{(m+1)(m+2)} = \frac{m+1}{m+2} $$
Ami pontosan egyezik az elvárt $\frac{n}{n+1}$ képlettel az $n=m+1$ esetben.
20
Bizonyítsa be, hogy a $3^{2n+2} - 8n - 9$ kifejezés osztható 64-gyel minden $n$ pozitív egész számra.