unidad V

5.1 Y 5.1.1

INDUCCION Y PRINCIPIOS DE LA INDUCCION MATEMATICAS

En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

Premisa mayor: El número entero tiene la propiedad .

Premisa menor: El hecho de que cualquier número entero tenga la propiedad implica que también la tiene (que se anota ).

Conclusión: Todos los números enteros a partir de tienen la propiedad .

Ejemplo

Para todo , es un número que acaba en 6.

Sea la proposición: « acaba en 6».

Es claro que es cierto, porque .
Supongamos que es cierto para un valor de natural, y probemos .

Un entero acaba por 6 si se puede escribir así: , con entero positivo o igual a cero. La hipótesis es, pues, .

Entonces , con , entero.

Esta última escritura prueba que acaba por 6, o sea que es cierto.

Luego es cierto para todo .

La inducción es válida por la construcción misma del conjunto de los naturales mediante los axiomas de Peano. En este caso:

1 es un natural;
si lo es, entonces (sucesor de ) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la inducción transfinita, y la inducción sobre las fórmulas de la lógica proposicional.

Además de la demostración por inducción, existe la definición o construcción por inducción.

Ejemplo 2

Se tratara de demostrar por inducción la siguiente proposición:

1. Se comprueba para n=1

Se tiene por tanto que la proposición es verdadera para n=1

2. Hipótesis inductiva (n=h)

3. Tesis inductiva (n=h+1)

4. Demostración de la tesis con base en la hipótesis

Se aplica la hipótesis de inducción:

(sacando factor común)

Por lo tanto, por verificarse la proposición para n=1 y para n=k+1 siendo k cualquier número natural, la proposición se verifica

5.1.2 DEMOSTRACION MEDIANTE INDUCCION

Las ciencias experimentales siguen un modelo

Inductivo (

basándose enla observación de la naturaleza y utilizando un razonamiento de tipoinductivo para formular teorías generales), las matemáticas siguen unmodelo

deductivo.

Una teoría matemática parte de un conjunto dotadode relaciones u operaciones, para la cual se suponen ciertas algunasproposiciones. A las proposiciones que se suponen ciertas se lesdenominan

axiomas

y a partir de ellas se deducen otras denominadas

teoremas.

Los teoremas son entonces sentencias relativas a objetosmatemáticos formados por

hipótesis

(condiciones que se suponensatisfechas) y

tesis

(lo que se afirma que se cumple en dichascondiciones)Para lograr una prueba correcta de un teorema es esencial conocer bienlas reglas de deducción (razonamientos válidos) y el lenguajematemático así como tener un poco de intuición que desarrollaremosgeneralmente con la práctica.El ejercicio de la demostración de proposiciones matemáticas como el dela solución de problemas implica tal riqueza de actividades que esimposible unas normas generales que las abarquen. Sin embargo esconveniente el estudio de algunos tipos de demostración utilizados amenudo en las matemáticas.

Problema 1.

Demostrar que si n es un número entero positivo, entonces4n+15n−1 es múltiplo de 9.

Solución:

a) Primeramente, si n=1 entonces: 41+15(1)−1=18 y como 9∣18 se tiene que la afirmación es cierta.

b) Asumimos como hipótesis de inducción que 9∣(4n+15n−1), y debemos demostrar que 9∣(4n+1+15(n+1)−1).

En efecto:

4n+1+15(n+1)−1

=4n+1+15n+15−1

=4n+1−4n+(4n+15n−1)+15

=4n(4−1)+9k+15

con k∈N, por la hipótesis de inducción.

=3(4n)+9k+15

=3(3+1)n+15+9k

Aplicando Binomio de Newton:

=3(3n+32p+1)+15+9k; para algún p∈N

=9⋅3n−1+9⋅3p+18+9k

=9(3n−1+3p+2+k)

⇒9∣[4n+1+15(n+1)−1]■

Problema 2.

Demuestre que si n∈N, entonces:

1+12+13+14+⋯+12n−1>n2.

Solución:

a) Si n=1 se tiene que 1>12 lo cual es cierto.

b) Asumimos ahora que:

1+12+13+14+⋯+12n−1>n2

y habrá que utilizar esto para demostrar que:

1+12+13+14+⋯+12n−1+12n+12n+1+⋯+12n+1−1>n+12.

Pero aplicando la hipótesis de inducción, basta probar que

12n+12n+1+⋯+12n+1−1≥12.

Esta última expresión contiene [2n+1−1−(2n)]+1=2nfracciones. Pero entonces:

12n+12n+1+⋯+12n+1−1≥12n+1+12n+1+⋯+12n+1

repitiéndose la fracción 12n+1 en el segundo término 2n veces.

⇒12n+12n+1+⋯+12n+1−1≥2n⋅12n+1=12■

Problema 3.

Demuestre que si n∈N, y

Sn=01!+12!+23!+⋯+n−1n!,

entonces Sn=n!−1n!.

Solución:

a) Sea n=1, S1=01!=0=1!−11!.

b) Asumimos ahora que para n=p, Sp=p!−1p!.

Hay que demostrar que para n=p+1, Sp+1=(p+1)!−1(p+1)!.

Pero, por definición:

Sp+1=01!+12!+23!+⋯+p−1(p)!+p(p+1)!,

y al aplicar la hipótesis te inducción:

=p!−1p!+p(p+1)!

=(p!−1)(p+1)+p(p+1)!

=p⋅p!−p+p!−1+p(p+1)!

=p!(p+1)−1(p+1)!

=(p+1)!−1(p+1)!■

Problema 4.

Demuestre que si n∈N;n≥2 entonces

1√+2√+3√+⋯+n√>n.

Solución:

a) Sea n=2, tenemos (1√+2&radic2=1+22√+4.

⇒1√+2√=5+22√−−−−−−−√>4√=2

b) Tenemos como hipótesis inductiva que para n=k se cumple

1√+2√+3√+⋯+k√>k.

Hay que demostrar que, sea n=k+1, es cierto que

1√+2√+3√+⋯+k√+k+1−−−−−√>k+1.

Pero, utilizando la hipótesis inductiva:

1√+2√+3√+⋯+k√+k+1−−−−−√>k+k+1−−−−−√.

Y como:

(k+k+1−−−−−&radic2=k2+2kk+1−−−−−√+k+1>k2+2k+1

⇒k+k+1−−−−−√>k+1

⇒1√+2√+3√+⋯+k√+k+1−−−−−√>k+k+1−−−−−√>k+1

Por tanto ∀n∈N;n≥2,

1√+2√+3√+⋯+n√>n.■

Problema 5.

Demuestre que si n∈N entonces 3∣(10n+1+10n+1).

Solución:

a) Probemos que para n=1 se cumple:

101+1+101+1=21

3∣21.

b) Como hipótesis de inducción asumimos que para

n=k,3∣(10k+1+10k+1);

entonces hay que demostrar que

3∣(10n+1+10k+1+1).

Pero notemos que:

10k+2+10k+1+1

=10⋅10k+1+10⋅10k+1

=10(10k+1+10k)+1+10k+1+10k−10k+1−10k

=10(10k+1+10k)−1(10k+1+10k)+(10k+1+10k+1)

y aplicando la hipótesis te inducción:

=9(10k+1+10k)+3p; con algún p∈N

=3[3(10k+1+10k)+p]

con lo cual queda demostrada la tesis.

TEMA 3

5.2 Recursividad

5.2.1 Definiciones

5.2.2 Funciones recursivas

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

FUNCIÓN Factorial(n)

    VAR resultado: Entero

    SI (n<2) ENTONCES

        resultado = 1;

    SINO

        resultado = n * Factorial(n-1);

FSI

    RETORNA resultado;

FFUNCIÓN

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante uncaso base de la recursividad.

Las claves para construir un subprograma recurrente son:

Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Recursividad indirecta

Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y estas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.

Subrutina_A → Subrutina_B → Subrutina_A

Subrutina_A → Subrutina_B → Subrutina_C → Subrutina_D → Subrutina_A

Determine los términos del 2 al 6 de los números