mathematical induction

mathematical induction (tsz. mathematical inductions)

1. (informatika) teljes indukció

A Mathematical Induction (magyarul: teljes indukció) egy alapvető bizonyítási módszer a matematikában, amellyel állításokat bizonyítunk természetes számokra. Különösen hasznos akkor, amikor azt szeretnénk megmutatni, hogy egy adott állítás minden természetes számra igaz.

A matematikai indukció lényege: Ha tudjuk, hogy egy állítás igaz az első számra, és azt is, hogy ha igaz valamelyik számra, akkor igaz a rákövetkezőre is, akkor az állítás igaz minden természetes számra.

Ez egy láncreakció:

• Az első dominó (az első szám) eldől – indukció alapja
• Ha bármelyik dominó eldől, akkor eldől a következő is – indukciós lépés

Tegyük fel, ${\textstyle P(n)}$ egy állítás, amelyet minden ${\textstyle n\in \mathbb {N} }$ természetes számra be akarunk bizonyítani.

Bizonyítsuk be, hogy az állítás igaz az első számra: ${\textstyle P(1)}$ (vagy néha ${\textstyle P(0)}$, ha 0-tól indul)

Tegyük fel, hogy az állítás igaz valamilyen ${\textstyle k\in \mathbb {N} }$ esetén: (→ indukciós feltevés) ${\textstyle P(k)}$ igaz

Bizonyítsuk be, hogy ebből következik ${\textstyle P(k+1)}$ is: ${\textstyle P(k)\Rightarrow P(k+1)}$

Ekkor ${\textstyle P(n)}$ igaz minden természetes ${\textstyle n}$-re.

Minden természetes ${\textstyle n\geq 1}$ esetén igaz, hogy:

$${\displaystyle 1+2+3+\dots +n={\frac {n(n+1)}{2}}}$$

1. Indukció alapja: ${\textstyle n=1}$ Bal oldal: ${\textstyle 1}$ Jobb oldal: ${\textstyle {\frac {1\cdot (1+1)}{2}}=1}$ → igaz

2. Indukciós lépés: Tegyük fel, hogy:

$${\displaystyle 1+2+\dots +k={\frac {k(k+1)}{2}}}$$

Be kell bizonyítanunk, hogy:

$${\displaystyle 1+2+\dots +k+(k+1)={\frac {(k+1)(k+2)}{2}}}$$

Bal oldal az indukciós feltevés alapján:

$${\displaystyle {\frac {k(k+1)}{2}}+(k+1)={\frac {k(k+1)+2(k+1)}{2}}={\frac {(k+1)(k+2)}{2}}}$$

→ Ez pontosan a kívánt jobb oldal: ${\textstyle {\frac {(k+1)(k+2)}{2}}}$

3. Következtetés: Az állítás igaz minden ${\textstyle n\in \mathbb {N} ,n\geq 1}$ esetén.

Itt az indukciós lépéshez nemcsak ${\textstyle P(k)}$, hanem minden előző ${\textstyle P(i),i\leq k}$ is felhasználható.

Hasznos pl. Fibonacci-számokra vagy algoritmusokra.

Néha fordított irányban, nagyobból kisebb felé működik – ritkább.

• Sorozatok, rekurziók bizonyítása
• Oszthatósági problémák
• Gráfelmélet (pl. csúcsszám)
• Algoritmusok helyessége
• Kombinatorika (pl. binomiális tétel)
• Informatika (pl. programok helyességének bizonyítása)

Tétel: ${\textstyle 4^{n}-1}$ osztható 3-mal minden ${\textstyle n\geq 1}$ esetén.

Indukció alapja: ${\textstyle n=1}$: ${\textstyle 4^{1}-1=3}$, ami osztható 3-mal → igaz

Indukciós lépés: Tegyük fel: ${\textstyle 4^{k}-1}$ osztható 3-mal. Akkor:

$${\displaystyle 4^{k+1}-1=4\cdot 4^{k}-1=4(4^{k}-1)+3}$$

Mivel ${\textstyle 4^{k}-1}$ osztható 3-mal, és ${\textstyle 4(4^{k}-1)+3}$ is → következik, hogy ${\textstyle 4^{k+1}-1}$ is osztható 3-mal.

A teljes indukció egy strukturált, erős eszköz a matematikai állítások bizonyítására természetes számokra. Lépései: alap, feltétel, következmény. A számítástudományban és elméleti informatikában is kulcsszerepet játszik, különösen rekurzív struktúrák és algoritmusok helyességének bizonyításánál.

• mathematical induction - Szótár.net (en-hu)
• mathematical induction - Sztaki (en-hu)
• mathematical induction - Merriam–Webster
• mathematical induction - Cambridge
• mathematical induction - WordNet
• mathematical induction - Яндекс (en-ru)
• mathematical induction - Google (en-hu)
• mathematical induction - Wikidata
• mathematical induction - Wikipédia (angol)