Indukzio matematiko

Matematikan, indukzio matematikoaren printzipioa, $n$-ren menpean dauden proposizioak egia diren ala ez frogatzea ahalbidetzen duen arrazonamendua da. Kontuan harturik, $n$ zenbaki arrunt infinituko multzoaren barruan dagoela.

Arrazonamendua hurrengoa izango litzateke:

$P$ propietatea betetzen duen $n$ zenbaki arrunt bat hartuz, frogatu behar da edozein zenbaki $n$, $P$ propietatea izanik, inplikatzen duela $n+1$ zenbakiak ere propietatea beteko duela. Beraz $n$ baino handiagoak diren zenbaki guztiak $P$ propietatea beteko dute.

Historia

K.a. 370. urtean. C. Platonen Parmenideak froga induktibo inplizitu baten adibide goiztiar bat izan dezake. Kontrako teknika iteratu bat, gorantz beharrean beherantz kontatuz, soriteen paradoxan aurkitzen da, non argudiatzen zen 1.000.000 harea alek multzo bat osatzen bazuten, eta meta batetik ale bat kenduta pila bat bezala uzten bazuten, orduan hondar ale bakar batek (edo alerik ere ez) multzo bat osatzen duela.

Indian, indukzio matematiko bidezko lehen froga inplizituak Bhaskararen "metodo ziklikoan" eta al-Karajik 1000 urte inguruan idatzitako al-Fakhrin agertzen dira. C. Sekuentzia aritmetikoei aplikatu zien, binomioaren teorema eta Pascalen hirukiaren propietateak frogatzeko.

Hala ere, antzinako matematikari hauetako batek ere ez zuen esplizituki adierazi indukzioaren hipotesia. Antzeko beste kasu bat (Vaccak idatzi zuenaz bestera, Freudenthalek kontu handiz frogatu zuen bezala) Francesco Maurolicorena izan zen bere Arithmeticorum libri duo-n (1575) lanean, zeinak teknika erabili baitzuen lehen n oso bakoitien batura n2 dela frogatzeko.

Indukzioaren lehen erabilera zorrotza Gersonidesek egin zuen (1288-1344) [11] [12]. Indukzio-printzipioaren lehen formulazio esplizitua Pascalek eman zuen bere Traité du triangle arithmétique (1665) lanean. Beste frantses batek, Fermatek, antzeko printzipio bat erabili zuen zabal-zabal: zeharkako proba jaitsiera infinituaren bidez.

Indukzioaren hipotesia Jakob Bernoulli suitzarrak ere erabili zuen, eta ordutik oso ezaguna egin zen. Hasierako tratamendu formal modernoa ez zen XIX. mendera arte iritsi, George Boole, Augustus de Morgan, Charles Sanders Peirce, Giuseppe Peano eta Richard Dedekindekin .

Indukzioaren bidezko froga

Izan bedi $n$ zenbaki arrunten multzoa definituriko propietatea: $P(n)$

Izendatutako propietatea $n$ zenbaki arrunt guztietarako beteko da, hurrengo bi baldintzak betetzen badira:

$\qquad$(i) Oinarrizko kasua: $n=1$ denean, $P(n)$ egia izango da.

$\qquad$(ii) Edozein $n=k$ izanik, $P(k)$ egiazkoa bada (hipotesia) , $P(k+1)$ ere egia izango da (tesia).

Beraz, honekin froga daiteke $P(n)$ egia dela $n$ arrunt guztietarako

1. adibidea

Frogatu nahi da $P(n)$ egia dela, $n$ zenbaki arrunt guztientzako.

$P(n)=1+2+\cdots +n={\frac {n(n+1)}{2}}\,.$

$P(n)$ -k adierazten du, $n$ baino txikiagoak edo berdinak diren zenbaki arrunt guztien batura.

(i) OINARRIZKO KASUA: Frogatu behar da $n=1$ betetzen dela. Horretarako:

$P(1)={\displaystyle 1={\frac {1\cdot (1+1)}{2}}\,.}$

Eskuineko aldea ebatziz,

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

Beraz,

$P(1)=1$ frogatu nahi zen bezala.

(ii) $n=k$ dela kontuan hartuz, frogatu nahi da $P(k)$ egia bada $P(k+1)$ egia izango dela zenbaki arrunt guztietarako.

Horretarako, demagun $P(k)$ egia dela. Beraz, frogatu behar da $P(k+1)$ egia izango dela.

$P(k)=1+2+\cdots +k={\frac {k(k+1)}{2}}\,\Rightarrow P(k)=1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}\,$

Indukzio hipotesia ($P(k)$ egia da) erabiliz, ezkerreko terminoa berridatzi daiteke:

${\frac {k(k+1)}{2}}+(k+1)\,.$

Aurrekoa garatuz,

${\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {k^{2}+k+2k+2}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}}$

Horrela frogatuta gelditzen da $P(k+1)$ egia dela. Orduan, esan daiteke $P(n)$ bete egiten dela $n$ zenbaki arrunt guztietarako.

2. adibidea

Frogatu nahi da $P(n)$ egia dela, $n$ zenbaki arrunt guztientzako.

$P(n)=1\cdot 2\cdot 3\cdot \cdot \cdot n>2^{n}$

(i) OINARRIZKO KASUA: Frogatu behar da $n=4$ betetzen dela; izan ere $n<4$ den edozein zenbaki naturaletarako ez da baieztapena betetzen. Horretarako:

$P(4)=1\cdot 2\cdot 3\cdot 4>2^{4}\Longleftrightarrow 24>16$

(ii) $n=k$ hartuz, suposatuz $P(k)$ egia dela, frogatuko dugu $P(k+1)$ kasuan ere ezberdintza beteko dela $n>4$ edozein zenbaki arruntetarako. Hau da, ondorengo ondoriora iritsi nahi gara:

$P(k+1)=1\cdot 2\cdot 3\cdot \cdot \cdot k\cdot (k+1)>2^{k+1}$

Horretarako ezberdintzaren ezkerreko aldetik hasiko gara eskuinekora iritsi ahal izateko. Lehendabizi gure hipotesiaren bi aldeetan $(k+1)$ gaia biderkatuko dugu, frogatu nahi dugunaren ezkerreko aldearen itxura lortzearren:

$1\cdot 2\cdot 3\cdot \cdot \cdot k\cdot (k+1)>2^{k}(k+1)$

Orain argi ikus dezakegu $\forall k>4:(k+1)>2$ izango dela. Hori dela eta ondorengo ondorioa lortu dugu:

$1\cdot 2\cdot 3\cdot \cdot \cdot k\cdot (k+1)>2^{k}(k+1)>2^{k}\cdot 2$

Jakinik $2^{k}\cdot 2=2^{k+1}$ dela, frogatu nahi genuen adierazpenera iritsi gara:

$1\cdot 2\cdot 3\cdot \cdot \cdot k\cdot (k+1)>2^{k}(k+1)>2^{k}\cdot 2=2^{k+1}\Longleftrightarrow 1\cdot 2\cdot 3\cdot \cdot \cdot k\cdot (k+1)>2^{k+1}$

Bestelakoak

Praktikan, indukzio bidezko frogek egitura desberdinak izan ditzakete, frogatu nahi dugun propietatearen araberakoa izaten baita.

Oinarrizko kasua 0 edo 1 ez denean

Baieztapena b zenbaki natural batetik aurrera betetzen dela frogatu nahi dugunean, indukzio bidezko froga ondorengo itxura hartuko du:

(i) Oinarrizko kasua: $n=b$ denean, $P(n)$ egia izango da.

(ii) Edozein $n=k:k\geq b$ izanik, $P(k)$ egiazkoa bada (hipotesia) , $P(k+1)$ ere egia izango da (tesia).

Adibidez, 2ⁿ ≥ n + 5 beteko dela edozein n ≥ 3 -rako, aurreko egituraz baliatuko gara.

Indukzio sendoa

Indukzio sendoan ematen den aldaketa, hasierako hipotesia sendoago edo indartsuago izatea litzateke. Modu honetan, suposatuz $P(n)$ egia dela edozein $n<m+1$ -rako, frogatuko dugu $P(m+1)$ kasuan ere baieztapena betetzen dela. Hala ere, nahiz eta hartutako hipotesia sendoagoa izan, horrek ez du esan nahi indukzio matematikoaren ohiko egitura baino ondorio garrantzitsuago batera helduko garenik. Izan ere, 'sendoa' hitzak hipotesiari egiten dio erreferentzia. Beraz, bi metodoak baliokideak izango dira. Azken egitura honetan, $P(0)$ kasua frogatzea falta zaigu, eta batzuetan, $P(1),P(2)...$ oinarrizko kasu gehigarriak frogatzea komenigarria izaten da, argumentu orokorra aplikatu ahal izateko; adibidez Fibonacci F_n' zenbakietarako.

Kanpo estekak

• Datuak: Q178377
• Multimedia: Induction (mathematics) / Q178377