Saltar al contenido principal
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
LibreTexts Español

B.2: Inducción en

( \newcommand{\kernel}{\mathrm{null}\,}\)

Template:MathJaxZach

En su forma más simple, la inducción es una técnica utilizada para demostrar resultados para todos los números naturales. Utiliza el hecho de que al comenzar0 y sumar repetidamente eventualmente1 alcanzamos cada número natural. Entonces, para probar que algo es cierto para cada número, podemos (1) establecer que es cierto para0 y (2) mostrar que siempre que sea cierto para un númeron, también lo es para el siguiente númeron+1. Si abreviamos “númeron tiene propiedadP” porP(n) (y “númerok tiene propiedadP” porP(k), etc.), entonces una prueba por inducción queP(n) para todos n\Natconsta de:

  1. una prueba deP(0), y

  2. una prueba de que, para cualquierak, siP(k) entoncesP(k+1).

Para que esto quede claro como el cristal, supongamos que tenemos tanto (1) como (2). Entonces (1) nos dice que esoP(0) es cierto. Si también tenemos (2), sabemos en particular que siP(0) entoncesP(0+1), es decir,P(1). Esto se desprende de la declaración general “para cualquierak, si es queP(k) entoncesP(k+1)” poniendo0 parak. Entonces por modus ponens, tenemos esoP(1). De (2) otra vez, tomando ahora1 paran, tenemos: siP(1) entoncesP(2). Desde que acabamos de establecerP(1), por modus ponens, tenemosP(2). Y así sucesivamente. Para cualquier númeron, después de hacer estosn tiempos, finalmente llegamos aP(n). Entonces (1) y (2) juntos establecenP(n) para cualquiern\Nat.

Veamos un ejemplo. Supongamos que queremos saber cuántas sumas diferentes podemos lanzar conn dados. A pesar de que pueda parecer una tontería, comencemos con0 los dados. Si no tienes dados solo hay una suma posible que puedes “lanzar”: no hay puntos en absoluto, que suma a0. Entonces el número de diferentes lanzamientos posibles es1. Si solo tienes un dado, es decir,n=1, hay seis valores posibles,1 a través de6. Con dos dados, podemos lanzar cualquier suma de2 a través12, eso es11 posibilidades. Con tres dados, podemos lanzar cualquier número desde3 hasta18, es decir,16 diferentes posibilidades. 1,6,11,16: parece un patrón: ¿tal vez la respuesta es5n+1? Por supuesto,5n+1 es el máximo posible, porque solo hay5n+1 números entren, el valor más bajo que puedes lanzar conn dados (todos1) y6n, el más alto puedes lanzar ( 6todos's).

TeoremaB.2.1

Conn los dados se pueden lanzar todos los valores5n+1 posibles entren y6n.

Comprobante. P(n)Sea el reclamo: “Es posible lanzar cualquier número entren y6n usandon dados”. Para utilizar la inducción, demostramos:

  1. La base de inducciónP(1), es decir, con un solo dado, puedes lanzar cualquier número entre1 y6.

  2. El paso de inducción, para todosk, siP(k) entoncesP(k+1).

(1) Se prueba inspeccionando una matriz6 de lados. Tiene los 6 lados, y cada número entre1 y6 aparece en uno de los lados. Por lo que es posible lanzar cualquier número entre1 y6 usando un solo dado.

Para probar (2), asumimos el antecedente del condicional, es decir,P(k). Esta suposición se denomina hipótesis inductiva. Lo usamos para probarP(k+1). Lo difícil es encontrar una manera de pensar sobre los posibles valores de un lanzamiento dek+1 dados en términos de los posibles valores de lanzamientos dek dados más de tiros de tiros del extrak+1 -st die—esto es lo que tenemos que hacer, sin embargo, si queremos usar el inductivo hipótesis.

La hipótesis inductiva dice que podemos obtener cualquier número entrek y6k usandok dados. Si lanzamos un1 con nuestro(k+1) -st morir, esto se suma1 al total. Entonces podemos lanzar cualquier valor entrek+1 y6k+1 lanzando5 dados y luego rodando un1 con el(k+1) -st dado. ¿Qué queda? Los valores6k+2 a través de6k+6. Podemos obtener estos rodandok6 s y luego un número entre2 y6 con nuestro(k+1) -st morir. Juntos, esto significa que con losk+1 dados podemos lanzar cualquiera de los números entrek+1 y6(k+1), es decir, hemos probadoP(k+1) usando la suposiciónP(k), la hipótesis inductiva. ◻

Muy a menudo usamos la inducción cuando queremos probar algo sobre una serie de objetos (números, conjuntos, etc.) que a su vez se define “inductivamente”, es decir, definiendo el(n+1) -st objeto en términos deln -th. Por ejemplo, podemos definir la sumasn de los números naturales hastan pors0=0sn+1=sn+(n+1)

Esta definición da:s0=0,s1=s0+1=1,s2=s1+2=1+2=3s3=s2+3=1+2+3=6, etc.
Ahora podemos probar, por inducción, esosn=n(n+1)/2.

ProposiciónB.2.1

sn=n(n+1)/2.

Comprobante. Tenemos que probar (1) esos0=0(0+1)/2 y (2) sisk=k(k+1)/2 entoncessk+1=(k+1)(k+2)/2. (1) es obvio. Para probar (2), asumimos la hipótesis inductiva:sk=k(k+1)/2. Usándolo, tenemos que demostrarlosk+1=(k+1)(k+2)/2.

¿Qué essk+1? Por la definición,sk+1=sk+(k+1). Por hipótesis inductiva,sk=k(k+1)/2. Podemos sustituir esto en la ecuación anterior, y luego solo necesitamos un poco de aritmética de fracciones:sk+1=k(k+1)2+(k+1)==k(k+1)2+2(k+1)2==k(k+1)+2(k+1)2==(k+2)(k+1)2.

La lección importante aquí es que si estás demostrando algo sobre alguna secuencia definida inductivamentean, la inducción es el camino obvio a seguir. E incluso si no lo es (como en el caso de las posibilidades de tiradas de dados), puedes usar inducción si de alguna manera puedes relacionar el casok+1 para con el caso parak.


This page titled B.2: Inducción en is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .

Support Center

How can we help?