Unidad 4 Inducción y Recursividad PDF

Preview

Summary

Download Unidad 4 Inducción y Recursividad PDF

Description

INDUCCIÓN MATEMÁTICA Y RECURSIVIDAD En muchos casos queremos demostrar que alguna propiedad relativa a los números naturales es cierta. Para hacerlo podemos analizar algunos casos particulares -para algunos valores naturales- pero no podemos hacerlo con todos, pues son infinitos. Por ejemplo, si observamos la suma de los primeros números impares:

1=1 1+3=4 1+3+5=9 1 + 3 + 5 + 7 = 16 ¿Notás algo en particular? Observá bien los resultados... Vemos que todos son cuadrados perfectos:

1 = 1 = 12 1 + 3 = 4 = 22 1 + 3 + 5 = 9 = 32 1 + 3 + 5 + 7 = 16 = 4 2 Por lo tanto, si agregamos otro número impar seguramente obtendremos 52 = 25 y así sucesivamente. Pero, ¿podemos estar seguros de ello? ¿Se cumplirá realmente con cualquier cantidad de impares sumados? Para poder responder con certeza a este interrogante y muchos similares vamos a utilizar la Inducción Matemática , que estudiaremos en esta sección. Para comenzar definiremos conjunto inductivo y conjunto de números naturales, así como la relación entre ambos.

¿Qué es un conjunto inductivo? Sea R el conjunto de los números reales, dado

A

, decimos que A es inductivo si:

1) 1 A 2) x A ⇒ x+1 A

¿Qué ¿Qué es es elel conjunto conjunto de de números números naturales? nat naturales? =

IA

tal que A es inductivo

A R

O sea que… el conjunto de los números naturales es la intersección de todos los conjuntos inductivos. Es el más pequeño de los conjuntos inductivos en el sentido de la inclusión.

1

Una herramienta que podemos utilizar para demostrar propiedades relativas al conjunto de los naturales es la inducción completa.

Principio Principio de de Inducción Inducción Completa Completa (PIC) (PIC) . Sea p(n) un predicado o función proposicional con dominio en el conjunto

de los números naturales

Si: 1) v [ p(1) ] = V

2) v [ p(h) ] = V ⇒ v [ p(h+1) ] = V Entonces: todas las p(n) son verdaderas.

Tengamos presente que: a)

el paso 1) se llama PASO BASE de la inducción y consiste en evaluar la proposición con n = 1

b) el paso 2) se llama PASO INDUCTIVO El antecedente de 2) se llama HIPOTESIS INDUCTIVA y el consecuente es la TESIS INDUCTIVA La hipótesis inductiva consiste en tomar como válida la propiedad en un determinado valor de n que llamamos h. A partir de esto, se debe probar la tesis inductiva, o sea que la propiedad es válida para el valor siguiente de h, es decir para h+1.

Tengamos Tengamos en en cuenta cuenta que que este este método método se se puede puede usar usar aunque aunque no no se se comience comience con con n=1 n=1 Dado m Si :

1: 1) v [ p(m) ] = V

2) v [ p(h) ] = V ⇒ v [ p(h+1) ] = V Entonces: p(n) es verdadera para todo n

m.

Veamos algunos ejemplos del proceso de inducción Ejemplo 1 n

Demostrar que:

∑

k k! = ( n+1 )! – 1

n

k 1

¿Qué significa el símbolo ∑ y el signo de admiración? Vayamos de a poco.

2

El símbolo ∑ indica sumatoria, es decir, una suma de varios términos. Debajo del signo hay una letra que es el contador igualado a su valor inicial. Arriba del signo se escribe el valor final del contador; luego, se reemplaza en la expresión por los sucesivos valores del contador y se suman. Por ejemplo: 5

∑

n2 = 12 + 22 + 32 + 4 2 + 52 = 1 + 4 + 9 + 16 + 25 = 55

n 1 3

∑

n 2n = 1 2 1 + 2 2 2 + 3 2 3

n 1

Ahora veamos el signo de admiración; este signo es el símbolo de factorial. ¿Qué ¿Qué es es elel factorial factorial de de un un número? número? Se llama factorial de un número natural a otro número natural que se obtiene multiplicando todos los naturales anteriores al dado. En forma recursiva se define: 0! = 1

n! = (n-1)! n

Ejemplos: 4! = 4 3! = 4 3 2! = 4 3 2 1! = 4 3 2 1 0! = 24 5! = 5 4! = 5 24 = 120

Solución: Paso base: n = 1: 1

p(1):

∑

k k! = ( 1+1 )! – 1

k 1

Vamos a analizar el valor de verdad de p(1). Para ello calculamos ambos miembros por separado y luego comparamos:

Primer miembro de p(1): 1 1! = 1 Segundo miembro de p(1): (1+1)! - 1 = 2! - 1 = 2 - 1 = 1 Como los dos miembros son iguales, entonces v [p(1)] = V

Paso inductivo: h

Hipótesis Inductiva: n = h

∑

k k! = ( h+1 )! - 1

k 1

3

h 1

∑

Tesis Inductiva: n = h+1

k k! = ( h+1+1 )! - 1

k 1

Demostración: para demostrar la igualdad de la tesis partimos del primer miembro y trataremos de llegar al segundo.

h 1

∑

h

k k! =(1)

k 1

∑

k k! + (h+1) (h+1)! =(2) (h+1)! - 1 + (h+1) (h+1)! =(3)

k 1

= (4) (h+1)! (1+h+1) -1 = 4 (h+1+1)! -1 Así, llegamos al segundo miembro. Justificaciones:

(1) De los h+1 términos dejamos aparte el último de ellos (2) Utilizamos la hipótesis inductiva (3) Sacamos factor común (h+1)! entre primer y tercer términos (4) Usamos definición recursiva de factorial

Ejemplo 2:

Demostrar

n

3 : (2n)! > 8

n-1 2

n

Solución: Paso base: n = 3: (En este caso comenzamos de n=3 en vez de n=1 ya que lo dice el enunciado)

p(1): (2 3)! > 8 3-1 3 2 Veamos si p(1) es verdadera: Primer miembro de p(1): (2 3)! = 6! = 720 Segundo miembro de p(1): 83-1 3 2 = 64 9 = 576 Como 720 576, entonces v [p(1)] = V

Paso inductivo:

Hip. Ind.: n = h

(2h)! > 8h-1 h2

4

Tesis Ind: n = h+1

(2(h+1))! > 8h (h+1) 2

Demostración: para demostrar la tesis, partimos del primer miembro de la misma y trataremos de probar que es mayor que el segundo.

(2(h+1))! = (2h + 2)! = (1) (2h+2) (2h+1) (2h)! (2) (4h2 + 6 h + 2) 8 h-1 h2 (3) (h2 + 2 h + 1) 8h 8 -1 h 2 >(4) 8h (h+1) 2 8 -1 h 2 >(5) 8h (h+1) 2

(3)

Con lo cual quedó demostrado que: 2(h+1))! > 8h (h+1)2

Justificaciones de cada paso: (1) Usamos la definición recursiva de factorial (2) Distribuimos el producto de (2h+2)(2h+1) y utilizamos la hipótesis inductiva (3) Acotamos la expresión (4h2 + 6h + 2) por una expresión menor (h2 + 2 h + 1) ya que resulta conveniente para lo que debemos probar (4) Escribimos el cuadrado de una suma que teníamos desarrollado (5) Dado que como h 3 entonces h2 9 por lo tanto h2 8

SUCESIONES Una sucesión es una lista de objetos, uno después del otro, numerada en el orden creciente de los números naturales. Formalmente, una sucesión es una función f: Hay que tener en cuenta que en una sucesión: 1. Los elementos pueden o no repetirse. 2. A veces en vez de se puede tomar

0

Por ejemplo: S 1 : 1,4,9,16,25,...,n 2,.... S2 :1,-1,1,-1,1,-1,1,-1,......,(-1)n,... Notaciones:

S: a1,a 2,......,an ,......

S : ( ai )

i N

A continuación demostraremos un ejercicio de divisibilidad:

5 23 n - 18 n , n

5

Para demostrar esta propiedad vamos a utilizar inducción completa. Nos conviene escribir la proposición en forma de igualdad, de esta forma:

23n - 18n = 5 k

P(n):

k

Paso base:

n =1:

231 – 181 = 5 = 5 1

1

Paso inductivo:

k Hip. Ind: 23 h – 18h = 5 k h+1 h+1 = 5 t t Tesis Ind: 23 – 18 Dem./ 23 h+1 – 18 h+1 = 23h

23 – 18 h 18 = 23 h ( 5 + 18 ) – 18 h 18 =

= 5 23 h + 18 ( 23 h – 18h ) = 5 23 h + 18 5 k = 5 (23 h + 18 k ) = 5 t Pues 23h + 18 k

por ser productos y suma de enteros.

Por lo tanto, por principio de inducción, n

se cumple p(n) es verdadera

RECURSION

Una definición es recursiva si hace referencia a ella misma.

Por ejemplo: la definición de factorial es recursiva n! = n (n-1)! con 0! = 1 Lo mismo ocurre al dar una sucesión, es decir que también puede definirse en forma recursiva. Al definir el término general, se puede hacer referencia a términos anteriores.

Ejemplo: Sea la sucesión definida por:

an = 2 a n-1

con a1 = 4

Veamos algunos elementos de la sucesión: Ya sabemos que a1 = 4. calculemos el siguiente:

a2 = 2 a 1 entonces:

a2 = 2 4 = 8

6

Y el próximo es: a3 = 2 a 2 entonces: a3 = 2 8 = 16 Y así sucesivamente. En este caso es fácil darse cuenta que los elementos de la sucesión son todos potencias de 2, pero hay muchos casos donde no es tan sencillo descubrir la regla general a simple vista. A las sucesiones dadas en forma recursiva, se las llama relaciones o ecuaciones de recurrencia.

¿Qué significa resolver una relación de recurrencia? Significa encontrar una expresión del an que satisfaga la relación y que no sea recursiva.

Clasificación de relaciones de recurrencia: Orden:: es la mayor diferencia entre los subíndices de los elementos de la sucesión que figuran en la relación de Orden recurrencia. Es decir, el orden indica cuántos términos anteriores hay que conocer para obtener uno en particular. Grado:: es el mayor exponente al que están elevados los elementos de la sucesión que figuran en la relación de Grado recurrencia. Ecuación Homogénea: Homogénea: al igual que las ecuaciones algebraicas, las homogéneas son las que no tienen términos independientes; pero en este caso no necesariamente los términos independientes son constantes sino que todos aquellos en los que no figuran elementos de la sucesión. Por ejemplo los siguientes términos son independientes: 3 n, 4, n 2 , etc. Ecuación de coeficientes constantes: constantes: en estas ecuaciones ninguno de los coeficientes de los elementos de la sucesión dependen de n. Por el contrario, si alguno depende de n, se dice que la ecuación tiene coeficientes variables.

Algunos ejemplos: a) an = 3 a n-1 + 2n2 es de orden 1 (diferencia entre n y n-1), grado 1 o lineal (exponentes 1), no homogénea (pues figura el término 2n2 ) y de coeficientes constantes (1 y 3). b) an = an-1 + a n-2 es de orden 2, lineal, homogénea y de coeficientes constantes. c) a n3 = 2 a n-1 – 1 es de orden 1, grado 3, no homogénea y coeficientes constantes. d) 2 an = n an-2 es de orden 2, lineal, homogénea y de coeficientes variables (n)

Vamos a analizar ahora las relaciones de recurrencia de orden 1 y de orden 2, homogéneas con coeficientes constantes y sus respectivas resoluciones

Relaciones de recurrencia lineales de orden 1, homogéneas Son de la forma: an = k a n-1 siendo k una constante real no nula.

7

Resolución: Supongamos que conocemos el valor de a0 . Cuánto vale el a1 ? Y a2? a 2 = k a 1 que a su vez es

a2 = k k a0 = k2 a0

Y a3? a 3 = k a 2 que a su vez es

a3 = k k k a0 = k3 a0

O sea que pareciera que:

a1 = k a 0

an = k n a 0

Pero para estar seguros de la fórmula encontrada, debemos demostrarla. Vamos a hacerlo por medio de Inducción Completa.

¿Qué es lo que hay que demostrar? Dato Dato del del ejercicio: ejercicio: la fórmula recursiva an = k an-1 y el valor de a 0 Fórmula encontrada no recursiva: an = kn a0 Lo que debemos probar es que la nueva fórmula define la misma sucesión que la otra. Paso base: n = 0 (ya que el primer término es a0 ) Lo calculamos con la nueva fórmula: a0 = k 0 a0 = a 0 entonces se cumple p(0) es V

Paso inductivo:

ah = k h a0 Hip. Ind: n = h Tesis Ind: n = h+1 a h+1 = k h+1 a0 Dem./ ah+1 = k ah = k k h a 0 =kh+1 a 0

Por dato del ejercicio

Hip. Ind.

Producto de potencias de igual base

Por lo tanto, queda demostrado que n N 0: p(n) es verdadera Ejemplo: La siguiente relación de recurrencia: 3 a n - 5 an-1 = 0 con a 0 = 4

8

Es equivalente a:

an =

Tiene por solución:

an =

5 a n-1 3

 5   .4  3

Relaciones de recurrencia lineales de orden 2, homogéneas Son de la forma:

cn an + c n-1 a n-1 + c n-2 a

n-2 =

0

Resolución: Supongamos que an = x n es una solución de la ecuación. Por lo tanto debe satisfacerla:

cn xn + cn-1 xn-1 + cn-2 xn-2 = 0 Sacamos factor común ... y obtenemos:

xn-2 ( cn x 2 + cn-1 x + cn-2 ) = 0 Como x no puede ser cero, entonces debe ser c n x2 + c n-1 x + cn-2 = 0 Lo cual es una ecuación algebraica de segundo grado que se llamaecuación ecuac ecuación característica. característica.

reales y distintas reales e iguales (una raíz doble) complejas conjugadas

Sus raíces pueden ser

Según sean las raíces de la ecuación característica, la solución general será: Reales distintas:

an = k1 r1n + k2 r 2n

Reales iguales:

a n = k1 r1n + k 2 n r1n

Complejas: ídem primer caso pero se opera con De Moivre (no se consideran en esta materia)

Las constantes k1 y k2 se calculan con los datos iniciales

Importante: Para poder resolver una relación de recurrencia de orden n se necesitan conocer n condiciones iniciales. Veamos dos ejemplos: Ejemplo 1

an - 5 a n-1 + 6 a n-2 = 0

con a0 = 3 y a1 = 5

9

Directamente planteamos la ecuación característica: x2 - 5 x + 6 = 0 r 1 = 2 y r2 = 3 Calculamos sus raíces, que son: Resultaron ser raíces REALES y DISTINTAS n n Planteamos la forma de la solución general: an = k1 r1 + k 2 r 2 Y ahora, teniendo en cuenta las condiciones iniciales: a0 = 3 entonces 3 = k 1 r10 + k 2 r 20 o sea k1 + k 2 = 3 a1 = 5 entonces 5 = k 1 r11 + k 2 r 21 o sea 2 k1 + 3 k 2 = 5 Nos ha quedado un sencillo sistema de ecuaciones lineales. Al resolverlo obtenemos: k1 = 4 y k2 = -1 Por lo tanto, nuestra solución es: an = 4 2 n - 3n Ejemplo 2:

an+2 = 4 an+1 - 4 an con a0 = 1 y a1 = 5 La ecuación característica es: x2 - 4 x + 4 = 0 que tiene como raíces: r1 = 2 y r2 = 2 O sea que son raíces REALES e IGUALES n n Planteamos la forma de la solución general: an = k1 2 + k 2 n 2 Y ahora, teniendo en cuenta las condiciones iniciales: a0 = 1 entonces k1 = 1 a1 = 5 entonces 2 k 1 + 2 1 k 2 = 5 entonces: k2 = 1.5

Por lo tanto, nuestra solución es:

a n = 2 n + 1.5 n 2 n

Demostración por Inducción: Paso base: Por ser de segundo orden hay que probar los dos datos iniciales: n = 0: a0 = 20 + 1.5 0 2 0 = 1 n = 1: a1 = 21 + 1.5 1 2 1 = 2 + 3 = 5 se verifica Paso inductivo: a h = 2h + 1.5 h 2 h ah-1 = 2 h-1 + 1.5 (h-1) 2 h-1 Tesis Ind: n = h+1 a h+1 = 2h+1 + 1.5 (h+1) 2 h+1 Hip. Ind: n = h

Dem./ Comenzamos desarrollando el primer miembro de la tesis: ah+1 = 4 a h – 4 ah-1 = 4 ( 2 h + 1.5 h 2 h ) – 4 ( 2 h-1 + 1.5 (h-1) 2 h-1 ) = = 4 2 h + 6 h 2 h – 4 2 h-1 - 6 (h-1) 2 h-1 = 4 2 h + 6 h 2h – 2 2 h - 3 h 2 h + 3 2 h = = 4 2 h + 6 h 2 h – 2 2 h - 3 h 2 h + 3 2h = 5 2 h + 3 h 2 h ( expresión 1) Ahora desarrollamos el segundo miembro de la tesis: 2h+1 + 1.5 (h+1) 2 h+1 = 2h 2 + 1.5 =5 2 h + 3 h 2 h (expresión 2)

h 2 h 2 + 1.5

2h 2 = 2 2 h + 3 h 2 h + 3 2h =

10

Como ambas expresiones son iguales, ha quedado probada la tesis. Y por principio de inducción: n N 0: p(n) es verdadera

Relaciones recurrencia con raíces complejas Observación: cuando los ceros de la ecuación característica son números complejos, para hallar la solución general debemos usar la fórmula que nos brinda el Teorema de Moivre1 . La expresión polar de un número complejo es z= x + y i= r (cos + i sen ) El teorema de Moivre se usa para calcular la potencia enésima de un número complejo y tiene la siguiente expresión: zn= rn (cos n + i sen n ) (que puede probarse usando inducción). En el caso que tengamos que resolver una ecuación de recurrencia donde las raíces de la ecuación característica sean complejas, sólo hallaremos, en este curso, la solución general ya que para calcular las soluciones particulares es necesario poner en juego saberes previos que no tenemos. Ejemplo

Para an = 2 an-1 – 2 an-2 El polinomio característico es p(x)= x2 -2x + 2 Los ceros de la ecuación característica son: 1r = 1 + i, r2= 1 –i La solución general es an = A(1 + i)n + B( 1 –i)n .

Relaciones de recurrencia lineal no homogénea Llamamos relación de recurrencia lineal no homogéneas de orden k, con coeficientes constante, a una expresión de la forma siguiente: an = k1 an-1 + k2an-2 +...+ k r an-r con n

r (I)

donde i=0,k , los k i son números reales n k, n N an=f(n) Si f(n)= 0 es homogénea

Algunos ejemplos: a)

1 Se

a n = 2a

n-1

+ 3( 2 n)

utiliza para calcular las raíces de un número complejo

11

2

b)

an + 2a n-1 = n - n -1

c)

a n - 2a n-1 + a n-2 = 3

¿Cómo se resuelven? 1) Dada (I) (que es la ecuación de recurrencia que se quiere resolver), llamamos relación de recurrencia homogénea asociada a (I) a la siguiente:

0= k1an-1 + k2 an-2 +...+ kr an-r con n

r

(II)

2) Aceptamos , sin demostrar, la siguiente propiedad:

Cualquier solución (an) de (I), para determinadas condiciones iniciales puede escribirse como: an = pn + h n hn es la solución de homogénea asociada pn es una solución particular de (I) 3) Para hallar la solución particular de (I) , no hay una regla general, sino un conjunto de pautas 4) Algunos ejemplos: a)

an – 3 an-1 = 2 en este caso f(n) es una constante, no depende de n, se puede probar con an = A se sustituye en la ecuación y se obtiene: A – 3 A =2, de donde A= -1 , por lo tanto la solución particular buscada es an =-1 sólo resta buscar la solución de la homogénea asociada

b) an +1 - an = n , a2 =1, n≥2 (I) n

La homogénea asociada es an +1 - an =0, de donde an +1 = an cuya solución es K(1) La solución particular se puede pensar como un polinomio de grado 1, digamos A n + B, siendo B solución de la homogénea, por ser una constante de donde conviene multiplicar (A n + B) por la menor potencia de n que asegure la no existencia de constantes (en este caso n) Queda an = A n 2 + Bn , (I) se escribe an +1= an + n Se reemplaza y queda: 2

2

A(n +1) + B(n+1) = A n + Bn +n , operando y comparando los coeficientes de las potencia semejantes queda:

12

2

Para n : A = A, Para n: 2A +B = B+1 Para el término independiente: A +B = 0

1 , 2

1 2

La solución particular es:

1 2

2

 1    2

La solución de la homogénea asociada es k. La solución que se busca es:

1 2

2

 1    2

Usando las condiciones iniciales queda que c debe ser 0 y por lo tanto:

1 2 c)

2

 1    2

Si la ecuación es an = 3 an -1 + 5( 3n ) se puede proponer pn = A3n por lo tanto se modifica por pn= An3n y queda 5n3n como solución particular quedando como solución general: an = k3n + 5n3 n, donde el valor de k se obtiene aplicando las condiciones iniciales.

d) La siguiente tabla nos ayuda para encontrar la forma de la solución particular en algunos casos determinados F(n)

Solución particular

K

Constante

N

An + B

n

2

An 2 + Bn + C

nt t natural

Polinomio compl...