Inducció matemàtica

Archiu:Domen-indukto.png

Inducció matemàtica

En matemàtiques, la inducció és un raonament que permet demostrar proposicions que depenen d'una variable $n$ que pren una infinitat de valores sancers. En térmens simples, l'inducció matemàtica consistix en el següent raonament:

Donat un número entero $a$ que té la propietat $P$, i el fet de que si fins a qualsevol número entero $n$ en la propietat $P$ implique que $n+1$ també la té, llavors, els número entero a partir de $a$ tenen la propietat $P$.

La demostració està basada en l'axioma denominat principi de l'inducció matemàtica.

L'inducció matemàtica demostra que podem pujar tan alt com vullgam en una escala, si vàrem demostrar que podem pujar el primer escaló (el "case base") i que des de cada escaló podem pujar al següent (el "pas" inductivo).

Concrete Mathematics, pág. 3, marge (en anglés).

Història

En el Parmenides, de Platón del 370 a. C., potser es pot identificar un primerenc eixemple d'una explicació implícita de prova inductiva. La més antiga chafada de l'inducció matemàtica es pot trobar en la demostració de Euclides en el Plantilla:SIGLE sobre l'infinitud dels número primo i en la de Bhaskara I usant el seu «método cíclico».

Una tècnica reversa, contant regresivamente en lloc de ascendentemente, es pot trobar en la paradoxa sorites, en a on s'argumenta que si 1 000 000 de grans d'arena formen un montó i removent un gra del montó al mateix temps, est seguix sent un montó, llavors, fins a un sol gra (inclús cap gra d'arena) formaria un montó.

Una demostració implícita de l'inducció matemàtica para seqüències aritmètiques va ser introduïda per Al-Karaji en la seua obra Al-Fakhri escrita al voltant de 1000 d. C., usat per a provar el teorema del binomi i les propietats del triàngul de Pascal.

Cap d'estos antics matemàtics va explicitar l'hipòtesis inductiva. Un atre cas similar va ser el de Francesco Maurlico en el seu Arithmeticorom libri duo (1575), que va usar la tècnica per a provar que la suma dels n primers sancers impars és igual a n al quadrat.

La primera formulació explícita sobre el principi d'inducció va ser establida pel filòsof i matemàtic Blaise Pascal en la seua obra Traité du triangle arithmétique (1665). Un atre francés, Fermat, fa ampli us d'un principi relacionat per a una demostració indirecta del descens infinit. L'hipòtesis inductiva va ser també amprada pel suís Jakob Bernoulli i a partir de llavors va ser més coneguda.

El tractament de caràcter rigorós i sistemàtic aplega solament en el Plantilla:SIGLE en George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano i Richard Dedekind.

Demostracions per inducció

Cridem $P_n$ a la proposició, a on $n$ és el ranc.

• Base: Es demostra que $P_1$ és certa, açò és el primer valor que complix la proposició (iniciació de l'inducció).
• Pas inductivo: Es demostra que, si $P_n$ és certa, açò és, com a hipòtesis inductiva, llavors $P_{n+1}$ lo és també, i açò sense condició sobre el sancer natural $n$ (relació d'inducció. Indicat com $n\Rightarrow n+1$).

Després, demostrat açò, concloem per inducció, que $P_n$ és cert para tot natural $n$.

L'inducció pot escomençar per un atre terme que no siga $P_1$, digam per $P_{n_0}$. Llavors $P_n$ serà vàlit a partir del número $n_0$, és dir, per a tot natural $n\ge n_0$.

Eixemple 1

Es provarà que la següent declaració P (n), que se supon vàlida per a tots els número natural n.

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

P (n) dona una fòrmula per a la suma dels número natural menors o igual a n. La prova de que P (n) és verdadera per a tots els número natural procedix com seguix.

Base: Es mostra que és vàlida per a n = 1.

en P(1) es té:

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

En el costat esquerre de l'equació, l'únic terme és 1, llavors el seu valor és 1.
mentres que el terme dret, 1·(1 + 1)/2 = 1.
Abdós costats són iguals, n = 1. Llavors P(1) és verdadera.

Pas inductivo: Mostrar que si P(k) és verdadera, llavors P(k + 1) és verdadera. Com seguix:

Es assumix que P(k) és verdadera (per a un valor no específic de k). Es deu llavors mostrar que P(k + 1) és verdadera:

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

usant l'hipòtesis d'inducció P(k) és verdadera, el terme esquerre es pot reescriure:

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

Desenrollant:

$\begin{array}{cc}\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{array}$

mostrant de fet que P(k + 1) és verdadera.

ya que s'han realisat els dos passos de l'inducció matemàtica tant la base com el pas inductivo, la declaració P(n) es complix per a tot número natural $n$ Q.I.D.

Eixemple 2

Es tractarà de demostrar per inducció la següent proposició:

$\sum _{k=1}^n(2k-1)3^k=(n-1)3^{n+1}+3$ $\mathrm{\forall }n\in \mathbb{N}$

1. Es comprova per a n=1

$\sum _{k=1}^1(2k-1)3^k=(2\cdot 1-1)3^1=3=(1-1)3^{1+1}+3$

Es té per tant que la proposició és verdadera per a n=1

2. Hipòtesis inductiva (n=h)

$\sum _{k=1}^h(2k-1)3^k=(h-1)3^{h+1}+3$

3. Tesis inductiva (n=h+1)

$\sum _{k=1}^{h+1}(2k-1)3^k=(h+1-1)3^{h+1+1}+3$

$\sum _{k=1}^{h+1}(2k-1)3^k=h{3}^{h+2}+3$

4. Demostració de la tesis en base a l'hipòtesis

$\sum _{k=1}^{h+1}(2k-1)3^k=\sum _{k=1}^h(2k-1)3^k+(2(h+1)-1)3^{h+1}$

S'aplica l'hipòtesis d'inducció:

$\sum _{k=1}^{h+1}(2k-1)3^k=(h-1)3^{h+1}+3+[2(h+1)-1]3^{h+1}$

$\sum _{k=1}^{h+1}(2k-1)3^k=(h-1)3^{h+1}+3+(2h+2-1)3^{h+1}$

$\sum _{k=1}^{h+1}(2k-1)3^k=3^{h+1}(h-1+2h+1)+3$ (traent factor comú)

$\sum _{k=1}^{h+1}(2k-1)3^k=3^{h+1}3h+3$

$\sum _{k=1}^{h+1}(2k-1)3^k=h{3}^{h+2}+3$

Per lo tant és correcte l'afirmació, verificant-se la proposició per a $n=1$ i per a $n=k+1$ sent $k$ qualsevol número natural, la proposició es verifica $\mathrm{\forall }n\in \mathbb{N}$.

Eixemple 3

El teorema del binomi és el següent:

${(a+b)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}$ a on $a,b\in ℝ$ i $n\in \mathbb{N}$

Assimilem que el concepte de coeficient binomial és el següent:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

Per a demostrar la teorema del binomi pot verificar-se que per a $n=1$ és verdader

1. Es comprova per a $n=1$:

${(a+b)}^1=a+b$

$\sum _{k=0}^1(\genfrac{}{}{0ex}{}{1}{k}){\left(a\right)}^k{\left(b\right)}^{1-k}=a^0{b}^1+a^1{b}^0=a+b$

Per tant, és cert per a $n=1$

Sabent que per a $n=1$ la teorema es complix es deu demostrar que és verdader per a $n+1$

2. Suponent cert per a $n$, es comprova per a $n+1$

$(a+b{)}^{n+1}=(a+b)(a+b{)}^n=(a+b)\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}=$

$=a\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}+b\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}=$

$=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{k+1}{b}^{n-k}+\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{(n+1)-k}=$

$=a^{n+1}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k-1})a^k{b}^{(n+1)-k}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{(n+1)-k}+b^{n+1}=$

$=a^{n+1}+\sum _{k=1}^n[(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})]a^k{b}^{(n+1)-k}+b^{n+1}=$

$=a^{n+1}+b^{n+1}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n+1}{k})a^k{b}^{(n+1)-k}=\sum _{k=0}^{n+1}(\genfrac{}{}{0ex}{}{n+1}{k})a^k{b}^{(n+1)-k}$

Com a resultat obtenim:

Plantilla:Caixa d'equació

La demostració està basada en l'axioma denominat principi de l'inducció matemàtica.

Eixemple 4

Proposta: Demostrar que tot número major o igual a 7 és suma d'un múltiple de 3 i un múltiple de 4.

Pas 1. (Base d'inducció)

Es demostra que l'afirmació és certa en el primer cas. 7 és suma d'un múltiple de 3 i un múltiple de 4, ya que $7=1*3+1*4$

Pas 2. (Base d'inducció)

Se supon que l'afirmació és certa per a un n i es deu mostrar que llavors és certa per a n+1.

Hipòtesis d'inducció

n és suma d'un múltiple de 3 i un múltiple de 4.

Demostració

Si $n=3r+4s$, llavors, $(n+1)=3r+4s+1$ i es necessita vore si açò és la suma un múltiple de 3 i un de 4. Efectivament, es complix que:

• $3r+4s+1=3(r-1)+4(s+1)$ si $r>0$
• $3r+4s+1=3(r+3)+4(s-2)$ si $r=0$

Com l'afirmació és certa per a un número n, dita afirmació serà certa per a un número n+1.

Eixemple 5

Proposta: Demostrar que $n!>2^n$ per a tota $n\ge 4$

Pas 1. (Base d'inducció)

$4!=24$ i $2^4=16$, per tant, $4!>2^4$

Pas 2. Hipòtesis d'inducció

Es partix de que $n!>2^n$. Es deu demostrar que $(n+1)!>2^{(n+1)}$

Demostració

Com $n\ge 4\iff (n+1)\ge 5$ , per tant, $2^n(n+1)\ge 2^n(5)>2^n(2)=2^{n+1}$.

Finalment: $(n+1)!>2^{n+1}$

Eixemple 6

Es deu demostrar que $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^n$

Pas 1. (Base d'inducció)

Per a n = 4, $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^4\iff 24>16$

Pas 2. Hipòtesis d'inducció

A pesar de que l'afirmació es complix per a n = 4, per a n = 1, n = 2 i n = 3 no es complix l'afirmació.

Llavors, si descartem estos valors, el treball a realisar és demostrar $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^n$ per a $n\ge 4$

Demostració

Per a demostrar que la desigualtat és vàlida per a k+1, és dir $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n(n+1)>2^{n+1}$ per a $n\ge 4$

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

Variants

En la pràctica, les demostracions per inducció s'estructuren a sovint de manera diferent, depenent de la naturalea exacta de la propietat a demostrar.

Case base distint de 0 o 1

Si es desija demostrar una afirmació no per a tots els número natural sino solament per a tots els números n majors o iguals a un cert número b, llavors la prova per inducció consistix en:

1. Mostrant que l'afirmació és vàlida quan n = b.
2. Mostrant que si l'afirmació és vàlida per a alguns n ≥ b llavors la mateixa declaració també és vàlida per a n + 1.

Açò pot usar-se, per eixemple, per a mostrar que 2ⁿ ≥ n + 5 per a n ≥ 3.

D'esta manera, es pot provar que alguna declaració P(n) és vàlida per a tots n ≥ 1, o inclús n ≥ -5. Esta forma d'inducció matemàtica és en realitat un cas especial de la forma anterior, perque si la declaració a provar és P(n) llavors provar-la en estes dos regles és equivalent a provar P(n + b) para tots els número natural n en un cas base d'inducció 0.

Inducció en més d'un contador

A voltes es requerix demostrar una afirmació que involucra dos número natural, n i m, per mig de la repetició del procés d'inducció. Açò és, un prova un cas base i un pas inductivo per a n, i en cada u d'ells prova un cas base i un pas inductivo per a m. També són possibles arguments més complicats que involucren tres o més contadors.

Descens infinit

El método del descens infinit és una variació de l'inducció matemàtica que va ser utilisada per Pierre de Fermat. S'utilisa per a mostrar que alguna afirmació Q(n) és falsa per a tots els número natural n. La seua forma tradicional consistix en mostrar que si Q(n) és cert per a algun número natural n, també ho és per a algun número natural m' estrictament més menut. Degut a que no hi ha seqüències infinites d'número natural que disminuïxquen, esta situació seria impossible, mostrant per contradicció que la Q(n) no pot ser certa per a cap n.

La validea d'este método pot ser verificada des del principi habitual de l'inducció matemàtica. Usant inducció matemàtica en la declaració P(n) definida com "Q(m) és falsa per a tots els número natural m menys que o igual a n", es deduïx que P(n) és vàlida per a tots n, lo que significa que Q(n) és falsa per a tots els número natural n.

Inducció forta

Una atra variant, cridada "inducció forta" (en contrast en la forma bàsica d'inducció que a voltes es coneix com "inducció dèbil") fa que el pas inductivo siga més fàcil de demostrar utilisant una hipòtesis més forta: un prova l'afirmació P(m + 1) baix la suposició de que P(n) es complix per a qualsevol número natural n menor que m + 1; pel contrari, la forma bàsica solament assumix P(m). El nom "inducció forta" no significa que este método puga provar més que "inducció dèbil", sino que simplement es referix a l'hipòtesis més forta utilisada en l'etapa inductiva; de fet, els dos métodos són equivalents. En esta forma d'inducció completa encara cal provar el cas base, P(0), i inclús pot ser necessari provar casos base adicionals com a P(1) ans que s'aplique l'argument general, com en el cas dels números de Fibonacci F_n.

L'inducció forta és equivalent a l'inducció matemàtica ordinària descrita anteriorment, en el sentit de que una demostració per un método pot transformar-se en una demostració per l'atre. Supongam que hi ha una prova de P (n) per inducció completa. Que Q(n) signifique "P(m) es complix per a tots m tal que 0 ≤ m ≤ n". Llavors Q(n) es complix per a qualsevol n si i solament si P(n) es manté per a qualsevol n, i la nostra demostració de P(n) es transforma fàcilment en una demostració de Q(n) per inducció (ordinària). Si, per un atre costat, P(n) haguera segut demostrat per inducció ordinària, la prova ya seria efectivament una per inducció completa: P(0) es prova en el cas base, sense usar suposicions, i P(n + 1) es prova en l'etapa inductiva, en la que es poden assumir tots els casos anteriors, pero només es necessita usar el cas P(n).

Eixemple

Per a este eixemple es pot partir de lo següent:

Siga $\phi$ una proposició dels naturals tal que para tot m en els naturals i para tot $k$ menor que $m$ es complix que $\phi (k)\Rightarrow \phi (m)$, llavors, per a tot $n$ en els naturals, $\phi (n)$ és cert.

Expressant-ho de forma matemàtica:

$\mathrm{\forall }m\in \mathbb{N}$ ( [$\mathrm{\forall }k<m$ $\phi (k)$] $\Rightarrow \phi (m)$ ) $\Rightarrow \mathrm{\forall }n\in \mathbb{N}$ $\phi (n)$.

Amprant el principi del bon orde:

• Supongam un conjunt A com el conjunt de tots els número natural que no complixen la proposició enunciada anteriorment => A = {$n\in \mathbb{N}|\mathrm{\neg }\phi (n)$} a on A no té mínim => $A=\varnothing$.

• L'objectiu és conseguir una contradicció partint de que A sí té mínim, per tant, m = min(A): $\mathrm{\forall }k<m(k\notin A)\wedge m\in A$.

• Per tant, de forma contradictòria, k no està en el conjunt A: $\mathrm{\forall }k<m(k\notin [n\in \mathbb{N}\mid \mathrm{\neg }\phi (n)])$ lo que comporta a que no es complixca la proposició $\phi$ => $\mathrm{\forall }k<m[\mathrm{\neg }(\mathrm{\neg }\phi (k))]=\mathrm{\forall }k<m[\phi (k)]$.
• Degut a que és fals que no es complixca $\phi (n)$ => $m\notin A$.

Per això, s'ha aplegat a la conclusió de que A no té mínim => $A=\varnothing$.

La propietat del bon orde

La validea de la inducció matemàtica està basada en el principi de bona ordenació dels conjunts de número entero no negatius.

Tot conjunt de sancers no negatius té un element mínim.

A sovint s'utilisa esta propietat directament en les demostracions.

Eixemple

Usa la propietat del bon orde per a demostrar l'algoritme de la divisió, recorda que l'algoritme de la divisió diu que si a és un número entero i d és un sancer positiu, llavors hi ha dos únics sancers c i r tals que 0 $\le$ r $\le$ d i a = dc + r.

Solució: Siga S el conjunt dels sancers no negatius de la forma a-dc, a on c és un sancer. Este conjunt no és buit, perque com veem -dc es pot engrandir tant com vullgam, això si, prenent c com un número entero que no siga negatiu en un valor absolut que siga gran, per la propietat del bon orde, S té mínim un element r=a-dc₀.

El sancer r no pot ser negatiu, també imaginem que r$\le$d, de no ser aixina, hi hauria un número que no seria negatiu menor en S. Per lo tant, existixen els sancers c i r', 0$\le$r$\le$d.

Vore també

• Recurrencia
• Número natural
• Paradoxa del cavall
• #Axioma de Peano

Enllaços externs

• Principle of Mathematical Induction en MathWorld.
• Plantilla:Planetmath
• Número natural, principi d'inducció
• Inducció Forta - Definició, Eixemples i Eixercicis - Àlgebra Superior 22
• AATA Principi d'Inducció