Vikipedio:Projekto matematiko/Matematika indukto

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Matematika indukto
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

Matematika indukto estas maniero de matematika pruvo tipe kutima fondi (tiu, ke, kiu) donita (propozicio, frazo, ordono) estas vera de ĉiuj naturaj nombroj, aŭ alie estas vera de ĉiuj (membroj, membras) de malfinia vico. Io pli ĝenerala (formo, formi) de argumento uzita en matematika logiko kaj komputiko (anstataŭas, anstataŭigas) la naturaj nombroj per alia bone--fundamentis (strukturoj, strukturas), kiel (arboj, arbas); ĉi tiu estas sciata kiel struktura indukto. Ĝi estas grava al (tononomo, noto, noti) (tiu, ke, kiu) matematika indukto estas rigora maniero de pruvo: estas ne (gradoj, gradas) de necerte. Fakte, matematika indukto estas tipo de _deductive_ (racianta, rezonanta, kaŭzanta). Ĉi tiu estas en kontrasto kun induktiva logiko, kiu estas iam argumentita kiel estante ne-rigora. (Vidi Problemo de indukto por pli.)

La unua sciata pruvo per matematika indukto (aperas, ŝajnas, aspektas) en _Francesco_ _Maurolico_'s _Arithmeticorum_ _libri_ _fuo_ ((1575, Kategorio:1575)). _Maurolico_ (pruvita, pruvis) (tiu, ke, kiu) la (sumo, sumi) de la unua n nepara (entjeroj, entjeras) estas n².

La plej simpla kaj plej komuna (formo, formi) de matematika indukto (demonstras, pruvas) (tiu, ke, kiu) (propozicio, frazo, ordono) tenas por ĉiuj naturaj nombroj n kaj konsistas de du (ŝtupoj, ŝtupas, paŝas):

La bazo: montranta (tiu, ke, kiu) la (propozicio, frazo, ordono) tenas kiam n = 1.
La indukta (ŝtupo, paŝi): montranta (tiu, ke, kiu) se la (propozicio, frazo, ordono) tenas por n = m, tiam la sama (propozicio, frazo, ordono) ankaŭ tenas por n = m + 1. (La propozicio sekva la vorto "se" estas (nomita, vokis) la indukta hipotezo. Ne (voko, voki) (ŝtupo, paŝi) 2 entute la indukta hipotezo.)

Ĉi tiu maniero (laboroj, laboras) per unua pruvanta la (propozicio, frazo, ordono) estas vera por startanta valoro, kaj tiam pruvanta (tiu, ke, kiu) la procezo kutima iri de unu valoro al la venonta estas valida. Se ĉi tiuj estas ambaŭ pruvita, tiam (ĉiu, iu) valoro povas esti ricevita per plenumante la procezo multfoje. Ĝi (majo, povas) esti helpema al (opinii, pensi) de la domeno efiki; se vi havi longa (linio, vico) de domeno (ludo) hirta kaj vi povas esti certa (tiu, ke, kiu):

La unua domeno estos fali.
Ĉiam domeno falas, ĝia venonta najbaro estos ankaŭ fali.

tiam vi povas konkludi (tiu, ke, kiu) ĉiuj domeno (ludo) estos fali.

Enhavo

1 Ekzemplo
- 1.1 Pruvo
2 (Ĝeneraligoj, Ĝeneraligas)
3 Pruvo aŭ _reformulation_ de matematika indukto
4 Ekstera (ligoj, ligas)
5 Referencoj

[redaktu] Ekzemplo

Supozi ni deziri al pruvi la (propozicio, frazo, ordono):

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

por ĉiuj naturaj nombroj n. Ĉi tiu estas simpla formulo por la (sumo, sumi) de la naturaj nombroj supren al la nombro n. La pruvo (tiu, ke, kiu) la (propozicio, frazo, ordono) estas vera por ĉiuj naturaj nombroj n procedas kiel sekvas.

[redaktu] Pruvo

Kontroli se ĝi estas vera por n = 1. Klare, la (sumo, sumi) de la unuaj naturaj nombroj estas 1, kaj 1(1 + 1) / 2 = 1. (Do, Tiel) la (propozicio, frazo, ordono) estas vera por n = 1. Ni povita difini la (propozicio, frazo, ordono) kiel P(n), kaj tial ni havi (tiu, ke, kiu) P(1) tenas.

Nun ni devi montri (tiu, ke, kiu) se la (propozicio, frazo, ordono) tenas kiam n = m, tiam ĝi ankaŭ tenas kiam n = m + 1. Ĉi tiu povas esti farita kiel sekvas.

Alpreni la (propozicio, frazo, ordono) estas vera por n = m, kio estas,

$1 + 2 + \cdots + m = \frac{m(m + 1)}{2}$

Adicianta m + 1 (kiu estas klare la (maldekstre, restis)-mano (flanka, latera) venonta (termo, membro, flanko, termino)) ambaŭflanken donas

$1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)$

Per algebra rego ni havi

$= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} = \frac{(m + 2)(m + 1)}{2}$

Tial ni havi

$1 + 2 + \cdots + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2}$

Ĉi tiu estas la (propozicio, frazo, ordono) por n = m + 1. Ĝi havas ne estas pruvita kiel vera: ni farita la supozo (tiu, ke, kiu) P(m) estas vera, kaj de (tiu, ke, kiu) supozo ni derivita P(m + 1). Signmaniere, ni havi montrita (tiu, ke, kiu):

$P(m) \Rightarrow P(m + 1)$

Tamen, per indukto:

Ni havi P(1), kio estas la ekvacio tenas se n havas la valoro de 1.
De ĉi tie, P(m) tenas por m = 1, sed P(m+1) havas estas (fondita, fondis). Tial, P(2) sekvas.
Kun P(2), P(3) sekvas; kaj kun P(3), P(4) (majo, povas) esti asertita.
Kaj tiel plu.
Ni (majo, povas) konkludi (tiu, ke, kiu) P(n) tenas por (ĉiu, iu) natura nombro n.

Kio estis pruvota

[redaktu] (Ĝeneraligoj, Ĝeneraligas)

[redaktu] Starti je b

Ĉi tiu tipo de pruvo povas esti ĝeneraligita en kelkaj (vojoj, vojas). Ekzemple, se ni bezono al pruvi (propozicio, frazo, ordono) ne por ĉiuj naturaj nombroj sed nur por ĉiuj nombroj pli granda ol aŭ egala al certa nombro b tiam:

Montranta (tiu, ke, kiu) la (propozicio, frazo, ordono) tenas kiam n = b.
Montranta (tiu, ke, kiu) se la (propozicio, frazo, ordono) tenas por n = m ≥ b tiam la sama (propozicio, frazo, ordono) ankaŭ tenas por n = m + 1.

Ĉi tiu povas esti uzita, ekzemple, al montri (tiu, ke, kiu) n² > 2n por n ≥ 3. En tiamaniere ni povas pruvi ankaŭ pretendas P(n) (tiu, ke, kiu) teni por ĉiuj n ≥0, aŭ (ebena, para, eĉ) n ≥-5. Ĉi tiu (formo, formi) de matematika indukto estas reale speciala okazo de la antaŭa (formo, formi) ĉar se la (propozicio, frazo, ordono) (tiu, ke, kiu) ni intenci al pruvi estas P(n) tiam pruvanta ĝi kun ĉi tiuj du reguloj estas ekvivalento kun pruvanta P(n + b) por ĉiuj naturaj nombroj n kun la unua du (ŝtupoj, ŝtupas, paŝas).

[redaktu] Alpreni vera por ĉiuj malpli granda (valoroj, valoras)

Alia ĝeneraligo, (nomita, vokis) plena indukto (aŭ forta indukto), permesas (tiu, ke, kiu) en la (sekundo, dua) (ŝtupo, paŝi) ni alpreni ne nur (tiu, ke, kiu) la (propozicio, frazo, ordono) tenas por n = m sed ankaŭ (tiu, ke, kiu) ĝi estas vera por n (pli minuskla, pli malgranda) ol aŭ egala al m.

Eble surprize, en ĉi tiu (formo, formi) de indukto, ĝi estas ne necesa al pruvi (tiu, ke, kiu) la propozicio estas vera en la unua (kesto, okazo)! Tio estas ĉar ĝi estas _vacuously_ vera (tiu, ke, kiu) la propozicio tenas totale (okazoj, skatoloj, kestoj, kestas, okazas) antaŭ la unua (kesto, okazo), simple ĉar estas ne (okazoj, skatoloj, kestoj, kestas, okazas) antaŭ la unua (kesto, okazo). (Tononomo, Noto, Noti) (tiu, ke, kiu) la pruvo tiam de la (ŝtupo, paŝi) (bezonas, bezonoj) povi laboro kun malplena antaŭaĵo; la unua pruvo pli supre estas ne de ĉi tiu speco (sed povas esti konvertita).

Ĉi tiu povas esti uzita, ekzemple, al montri (tiu, ke, kiu)

$\operatorname{fib}(n) = \frac{ \varphi^n - (-1/\varphi)^n }{\sqrt{5}}$

kie _fib_(n) estas la n^{(th, -a)} Fibonaĉi-nombroj kaj Φ = (1 + √5)/2 (la (do, tiel)-(nomita, vokis) ora proporcio). Donita (tiu, ke, kiu) _fib_(m + 1) = _fib_(m) + _fib_(m − 1), ĝi povas esti pruvita (tiu, ke, kiu) (tiu, ke, kiu) la (propozicio, frazo, ordono) tenas por m + 1 se ni povas alpreni (tiu, ke, kiu) ĝi jam tenas por ambaŭ m kaj m − 1. (De ĉi tie la pruvo de ĉi tiu idento postulas duopa bazo - ĝi postulas komenca manifestacio (tiu, ke, kiu) la idento estas vera por ambaŭ n = 0 kaj n = 1).

Ĉi tiu ĝeneraligo estas (justa, ĵus) speciala okazo de la unua (formo, formi):

estu P(n) esti la (propozicio, frazo, ordono) (tiu, ke, kiu) ni intenci al pruvi,
tiam pruvanta ĝi kun ĉi tiuj reguloj estas ekvivalento al pruvanta la (propozicio, frazo, ordono) "P(m) por ĉiuj m ≤ n" por ĉiuj naturaj nombroj n kun la unua du (ŝtupoj, ŝtupas, paŝas).

[redaktu] _Transfinite_ indukto

La lasta du (ŝtupoj, ŝtupas, paŝas) povas esti _reformulated_ kiel unu (ŝtupo, paŝi):

Montranta (tiu, ke, kiu) se la (propozicio, frazo, ordono) tenas por ĉiuj n < m tiam la sama (propozicio, frazo, ordono) ankaŭ tenas por n = m.

Ĉi tiu estas fakte la plej ĝenerala (formo, formi) de matematika indukto kaj ĝi povas esti montrita (tiu, ke, kiu) ĝi estas ne nur valida por (propozicioj, frazoj, ordonoj) pri naturaj nombroj, sed por (propozicioj, frazoj, ordonoj) pri eroj de (ĉiu, iu) bone-fundamentita aro, tio estas, aro kun parta ordo (tiu, ke, kiu) enhavas ne malfiniaj descendantaj ĉenoj (kie < estas difinita tia (tiu, ke, kiu) a < b (meznombroj, meznombras, signifas) (tiu, ke, kiu) a ≤ b kaj a ≠ b).

Ĉi tiu (formo, formi) de indukto, kiam aplikis al ordaj numeraloj (kiu (formo, formi) bonorda kaj de ĉi tie bone-fundamentita klaso), estas (nomita, vokis) _transfinite_ indukto. Ĝi estas grava pruva tekniko en aroteorio, topologio kaj aliaj kampoj.

Pruvoj per _transfinite_ indukto tipe (distingi, diferencigi) tri (okazoj, skatoloj, kestoj, kestas, okazas):

kiam m estas minimuma ero, kio estas estas ne ero (pli minuskla, pli malgranda) ol m
kiam m havas direkto (antaŭulo, antaŭanto), kio estas la aro de eroj kiu estas (pli minuskla, pli malgranda) ol m havas plej granda ero
kiam m havas ne direkto (antaŭulo, antaŭanto), kio estas m estas (do, tiel)-(nomita, vokis) limigo-orda numeralo

Severe parolanta, ĝi estas ne necesa en _transfinite_ indukto al pruvi la bazo, ĉar ĝi estas _vacuous_ speciala okazo de la propozicio (tiu, ke, kiu) se P estas vera de ĉiuj n < m, tiam P estas vera de m. Ĝi estas _vacuously_ vera precize ĉar estas ne (valoroj, valoras) de n < m (tiu, ke, kiu) povis servi kiel (kontraŭekzemploj, kontraŭekzemplas). Vidi tri formoj de matematika indukto por pli sur ĉi tiu punkto.

[redaktu] Pruvo aŭ _reformulation_ de matematika indukto

La principo de matematika indukto estas kutime komencita kiel aksiomo de naturaj nombroj, vidi Aksiomoj de peano. Tamen, ĝi povas esti (pruvita, pruvis) en iuj logikaj sistemoj; ekzemple, se jena aksiomo ((nomita, vokis) la bona orda principo por naturaj nombroj):

La aro de naturaj nombroj estas bonorda

estas (dungita, dungita).

La aldona aksiomo estas alternativa formulaĵo de principo de matematika indukto. Tio estas, la du estas ekvivalento. Vidi pruvo de matematika indukto.

[redaktu] Ekstera (ligoj, ligas)

Matematika Indukto, (Ekzemploj, Ekzemplas) je (tranĉi-la-nodo, tranĉi-la-nodon)

[redaktu] Referencoj

Donald Knuth. La Arto de Komputila Programado, Volumeno 1: Fundamenta (Algoritmoj, Algoritmas), Tria Redakcio. Addison-a-_Wesley_, 1997. ISBN 0-201-89683-4. Sekcio 1.2.1: Matematika Indukto, _pp_.11–21.

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Matematika_indukto_6128.html"

Kategorioj: Artikoloj por polurado kaj movo | Matematika logiko | Pruva teorio | Pruvoj