Álgebra clásica

(i) Si 1 ≥ n0 , entonces n0 = 1 y, por hipótesis, se tiene que p(n0 ) es verdad, luego, p(1) es verdadero y 1 ∈ I1.

(ii) Si 1

n0, entonces 1 ≥ n0 → p(1) es verdad, porque el antecedente es falso, luego 1 ∈ I1.

Tomemos ahora n ∈ I1, entonces n ∈

y n ≥ n0 → p(n), luego tenemos que (n + 1) ∈ y se presentan dos casos:

(i) Si n ≥ n0, entonces n + 1 ≥ n0 + 1, luego n ∈ I1 y n ≥ n0, entonces p(n) es verdad y, por la hipótesis del teorema, p(n + 1) es verdad, por lo tanto, (n + 1 ≥ n0 → p(n + 1)). Luego (n + 1) ∈ I1.

(ii) Si n

n0 se tiene n < n0 y, por lo tanto (n + 1) ≤ n0; luego:

(a) Si (n + 1) = n0, entonces como p(n0) es verdad por hipótesis se tendrá que (n + 1) ∈ I1.

(b) Si (n + 1) < n0, entonces (n + 1 ≥ n0 → p(n + 1) es verdad porque su antecedente es falso, por lo tanto, (n + 1) ∈ I1.

Hemos demostrado que I1 es un conjunto inductivo con lo que

⊆ I1, o sea ∀n ∈ (n ∈ I1), o mejor ∀n ∈ (n ≥ n0) p(n).

1.2.2 Segundo principio de inducción

El enunciado de este principio es el siguiente:

Sea p(n) una fórmula en n y n0 ∈

, entonces:

(i)

[p(n0) ∧ ∀n ∈

[(n > n0) (p(n0) ∧ p(n0 + 1) ∧ · · · ∧ p(n)) → p(n + 1)]]

↓

∀n ∈

((n > n0) p(n)).

(ii)

[p(1) ∧ ∀n ∈

[(p(1) ∧ p(2) ∧ ··· ∧ p(n)) → p(n + 1)]] → ∀n ∈ ( p(n)).

Nota:

Es claro que (ii) es un caso particular de (i).

1.2.3 Otros conceptos

A causa de lo que estudiaremos con posterioridad, es necesario entregar algunas definiciones inductivas; éstas son:

Definición 1.2.1 Sea n ∈

se define la función factorial (!) del modo siguiente:

1! = 1 ∧ (n + 1)! = n!(n + 1).

Definición 1.2.2 Sea f :

→ , se define la sumatoria desde k = 1 hasta k = n de los f (k) del modo siguiente:

Definición 1.2.3 Sea f :

→ , se define la productoria desde k = 1 hasta k = n de los f (k) del modo siguiente:

Definición 1.2.4 Sea p ∈

diremos que p es un número primo si:

∀n ∈

∀m ∈ (p = n · m → (n = 1 ∨ m = 1).

Definición 1.2.5 Sean p, q ∈

diremos que p y q son primos relativos si:

(∀r ∈

)(∀s ∈ )(∀t ∈ )[(p = r · s ∧ q = r · t) → (r = 1 ∨ r = −1)],

es decir, si el MCD(p, q) = 1

A continuación pasaremos a aplicar los principios de inducción resolviendo algunos problemas.

1.3 Problemas resueltos

Problema 1.3.1 Para el natural fijo n, calcular la suma:

S = 1 + 2 + 3 + ·· · + n.

Solución:

Se tiene:

y sumando miembro a miembro estas dos igualdades, se obtiene:

2S = (n + 1) + (n + 1) + (n + 1) + ·· · + (n + 1),

o sea:

2S = n(n + 1),

de donde:

S = 1 + 2 + 3 + ··· + n =

,

que es el resultado pedido.

Nota:

En el problema siguiente, haremos ver que esta fórmula es válida para todo número natural.

Problema 1.3.2 Demostrar que:

Solución:

Consideramos el conjunto:

haremos ver que este conjunto I es inductivo.

Que n = 1 ∈ I es evidente, pues:

Suponemos válido que n ∈ I, o sea:

Ahora deberemos probar que (n + 1) ∈ I, es decir:

En efecto, se tiene:

por lo tanto I es un conjunto inductivo. Esto quiere decir que:

Problema 1.3.3 Para el natural fijo n, calcular la suma:

S = 12 + 22 + 32 + ··· + n2.

Solución:

Se tiene:

y sumando miembro a miembro estas dos igualdades, se obtiene:

(n + 1)3 − 1 = 3(12 + 22 + 32 + ··· + n2) + 3(1 + 2 + 3 + ··· + n) + n,

o sea:

3(12 + 22 + 32 + ··· + n2) = (n + 1)3 − (n + 1) −

,

de donde se consigue:

por consiguiente:

Notas:

(1) En el problema siguiente, haremos ver que esta fórmula es válida para todo número natural.

(2) En lo sucesivo, por comodidad, no escribiremos en las soluciones siguientes el conjunto I (que deberá establecerse que es inductivo); sólo probaremos para n = 1, aceptaremos para n y demostraremos para n + 1.

Problema 1.3.4 Demostrar que:

Solución:

Para n = 1 es evidente, pues:

Suponemos el resultado válido hasta n, o sea:

Ahora deberemos probarlo para (n + 1), es decir:

En efecto, se tiene:

Problema 1.3.5 Para el natural fijo n, calcular la suma:

S = 13 + 23 + 33 + · ·· + n3.

Solución:

Se tiene:

sumando miembro a miembro estas dos igualdades y factorizando adecuadamente, se obtiene:

13 + 23 + 33 + ··· + n3 =

.

Nota:

En el problema siguiente, haremos ver que esta fórmula es válida para todo número natural.

Problema 1.3.6 Demostrar que:

∀n ∈

[13 + 23 + 33 + ··· + n3 = .

Solución:

A causa de la similitud con los problemas anteriores, la demostración queda a cargo del lector.

Problema 1.3.7 Demostrar que:

Solución:

Para n = 1 es evidente, pues:

1 = 12.

Suponemos el resultado válido hasta n, o sea:

1 + 3 + 5 + ··· + (2n − 1) = n2.

Ahora deberemos probarlo para (n + 1), es decir:

1 + 3 + 5 + ··· + (2n − 1) + (2n + 1) = (n + 1)2.

En efecto, se tiene:

1 + 3 + 5 + ··· + (2n − 1) + (2n + 1) = n2 + (2n + 1) = n2 + 2n + 1 = (n + 1)2.

Problema 1.3.8 Demostrar que:

∀n ∈

[(x − y) es divisor de (xn − yn)].

Solución:

Para n = 1 es evidente, puesto que x − y es factor de x − y. Suponemos ahora que x − y es divisor de xn − yn; deberemos establecer que x − y es divisor de xn + 1 − yn + 1.

Si a xn + 1 − yn + 1 le restamos y sumamos xyn, conseguiremos:

xn + 1 − yn + 1 = xn + 1 − xyn + xyn − yn + 1 = x(xn − yn) + yn(x − y).

Como cada término de esta última expresión es divisible por x − y, también lo es xn + 1 − yn + 1, lo que demuestra lo pedido.

Problema 1.3.9 Si a1 = a2 = 1 y an + 1 = 3an + an−1 (n ≥ 2), entonces an y an + 1 son primos relativos.

Solución:

Vemos que a1 y a2 son primos relativos. Aceptemos la propiedad hasta n y supongamos que an y an + 1 no son primos relativos, o sea, existe el máximo común divisor entre an y an−1 y es MCD[an, an + 1] = d ≠ 1, es decir, an + 1 = pd y an = qd y como an + 1 = 3an + an−1 resulta pd = 3qd + an−1, luego an−1 = (p − 3q)d, MCD[an, an−1]= d ≠ 1, lo que es una contradicción, puesto que

hemos aceptado que estos últimos son primos relativos.

Problema 1.3.10 Sea n ∈

, se considera yn = (3 + )n + (3 − )n. Demostrar que:

(1) yn + 1 = 6yn − 4yn−1.

(2) yn es entero.

(3) El siguiente entero mayor que (3 +

)n es divisible por 2n.

Solución:

Para (1)

Para (2)

y1 = (3 +

) + (3 − ) = 6 es entero.

y2 = (3 +

)2 + (3 − )2 = 2(9 + 5) = 28 es entero.

Supongamos que y1, y2, ·· · , yn son enteros; pues bien, como yn + 1 = 6yn −4yn−1 se sigue que yn + 1 es entero.

Para (3)

Si n = 1 el siguiente entero mayor que (3 +

) es 6, que es divisible por 21 = 2. Si n = 2, el siguiente entero mayor que (3 + )2 es 28, que es divisible por 22 = 4. Ahora como (3 − )n es decimal (o sea ∈]0, 1[), se deduce que yn es el siguiente entero mayor que (3 + )n. Si yn es divisible por 2n e yn - 1 es divisible por 2n−1, entonces por (1) se tendrá yn + 1 = 6yn − 4yn - 1 = 6 · 2np − 4 · 2n−1q = 2n + 1(3p − q).

Problema 1.3.11 Si a1 = −5, a2 = −26 y

∀n ≥ 3 : an = 5an−1 − 6an−2 + 5 · 2n−2,

entonces:

∀n ∈

: an = 3 · 2n − 2 · 3n − 5 · n · 2n−1.

Solución:

En este caso se tiene:

a1 = 3 · 2 − 2 · 3 − 5 · 1 · 20 = −5,

y también:

a2 = 3 · 22 − 2 · 32 − 5 · 2 · 21 = −26.

Por otro lado, resulta:

Problema 1.3.12 Demostrar que:

∀n ∈

: 834n − 2 · 972n + 1

es divisible por 16.

Solución:

Para n = 1 834 − 2 · 972 + 1 = 47.458.321 − 18818 + 1 = 47.439.504 = 16 · 2.964.969

Se supone para n

834n − 2 · 972n + 1

es divisible por 16.

Se demuestra para n + 1

834n + 4 − 2 · 972n + 2 + 1

es divisible por 16.

Demostración:

Problema 1.3.13 Demostrar que si n es impar, entonces 24 divide a:

n(n2 − 1)

Solución:

Para n = 1, que es impar

1(12 − 1) = 0

y 0 es divisible por 24.

Se supone para n = 2m − 1

(2m − 1)[(2m − 1)2 − 1]= 4m(2m − 1)(m − 1)es divisible por 24.

Se demuestra para n = 2m + 1 (2m + 1)[(2m + 1)2 − 1]= 4m(2m + 1)(m + 1) es divisible por 24.

Demostración:

Problema 1.3.14 Demostrar que:

Solución:

Para n = 1

Se supone para n

Se demuestra para n + 1

Demostración:

luego:

Problema 1.3.15 Demostrar que:

Solución:

Para n = 1

Se supone para n

Se demuestra para n + 1 que:

Demostración:

Pero:

(96n2 + 236n + 123) : (4n + 3) = 24n + 41 = 24(n + 1) + 17,

o sea:

(96n2 + 236n + 123) = (4n + 3) · (24(n + 1) + 17). (1.2)

De (1.1) y (1.2) se sigue el resultado, es decir:

Problema 1.3.16 Sea f :

→ la función definida recursivamente por