Probar que todo número natural n se escribe como suma de distintas potencias de 2,
incluyendo 2^0 = 1 (sugerencia: considerar la mayor potencia de 2 menor o igual a n).
Demostración por inducción:
Para demostrar esta propiedad, utilizaremos el método de inducción matemática. Este
método consiste en probar que una afirmación es cierta para un caso base y luego demostrar
que si es cierta para un caso arbitrario, también lo será para el siguiente.
Caso base (n = 1):
1 = 2^0
Por lo tanto, la afirmación es cierta para n = 1.
Hipótesis inductiva:
Supongamos que cualquier número natural menor que n se puede escribir como
suma de distintas potencias de 2.
Paso inductivo:
Sea k la mayor potencia de 2 menor o igual a n. Es decir, 2^k ≤ n < 2^(k+1).
Consideremos el número n - 2^k. Este número es menor que n, por lo que, según
nuestra hipótesis inductiva, se puede escribir como suma de distintas potencias de 2:
o n - 2^k = 2^a + 2^b + ... + 2^z
Sumando 2^k a ambos lados de la igualdad, obtenemos:
o n = 2^k + 2^a + 2^b + ... + 2^z
Como k es mayor que cualquier otro exponente a, b, z, todas las potencias de 2 en la
suma son distintas.
Conclusión:
Hemos demostrado que si la afirmación es cierta para n-1, también lo es para n.
Como el caso base (n=1) es cierto, por el principio de inducción matemática, la
afirmación es cierta para todo número natural n.
Ejemplo:
Tomemos el número 13. La mayor potencia de 2 menor o igual a 13 es 8 (2^3).
Restamos 8 a 13: 13 - 8 = 5.
5 se puede escribir como suma de distintas potencias de 2: 5 = 4 + 1 = 2^2 + 2^0.
Por lo tanto, 13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0.
Hallar una fórmula para el término general de las sucesiones (an), n ∈ N definidas a
continuación y probar su validez.
i) a0 = 2, a1 = 4, an+2 = 4 an+1 − 3 an para n ∈ N0.
ii) a0 = 1, a1 = 4, an+2 = 4 an+1 − 3 an para n ∈ N0.
iii) a0 = 1, a1 = 4, an+2 = 4 an+1 − 4 an para n ∈ N0.
Sucesión i) a0 = 2, a1 = 4, an+2 = 4 an+1 − 3 an, para n ∈
N0.
Observación: Al observar los primeros términos y la relación de recurrencia, podemos
intuir que esta sucesión podría ser una progresión aritmética o geométrica. Sin embargo, al
probar con diferentes valores de n, nos daremos cuenta de que no se ajusta a ninguno de
estos patrones.
Solución: En este caso, no es tan evidente encontrar una fórmula cerrada para el término
general. Una forma de abordar este tipo de problemas es buscar una solución de la forma an
= r^n. Sustituyendo esta forma en la relación de recurrencia, obtenemos una ecuación
característica:
r^2 = 4r - 3
Resolviendo esta ecuación cuadrática, encontramos que las raíces son r = 1 y r = 3. Por lo
tanto, la solución general de la relación de recurrencia es de la forma:
an = A * 1^n + B * 3^n
Para determinar los valores de A y B, utilizamos las condiciones iniciales:
a0 = 2 = A + B
a1 = 4 = A + 3B
Resolviendo este sistema de ecuaciones, obtenemos A = 1 y B = 1.
Por lo tanto, el término general de la sucesión es:
an = 1 + 3^n
Demostración por inducción:
Caso base: Para n = 0 y n = 1, la fórmula coincide con los valores dados.
Hipótesis inductiva: Supongamos que la fórmula es válida para n = k y n = k+1.
Paso inductivo: Queremos demostrar que la fórmula también es válida para n =
k+2. a(k+2) = 4a(k+1) - 3a(k) Sustituyendo por la fórmula general y realizando las
operaciones, se obtiene: a(k+2) = 1 + 3^(k+2) Lo cual demuestra que la fórmula es
válida para n = k+2.
para todo n ∈ N0.
Por lo tanto, por el principio de inducción matemática, la fórmula an = 1 + 3^n es válida
Las sucesiones ii) y iii) se resuelven de manera similar.
∈ N0.
Sucesión ii) a0 = 1, a1 = 4, an+2 = 4 an+1 − 3 an, para n
La única diferencia con la sucesión i) es el valor inicial de a0. Siguiendo el mismo
procedimiento, se obtiene:
an = 3^n
∈ N0.
Sucesión iii) a0 = 1, a1 = 4, an+2 = 4 an+1 − 4 an, para n
En este caso, la ecuación característica tiene una raíz doble r = 2. Por lo tanto, la solución
general es de la forma:
an = A * 2^n + B * n * 2^n
Utilizando las condiciones iniciales, se obtienen los valores de A y B, y se encuentra el
término general.
Importante:
Generalización: Este tipo de problemas se resuelven encontrando la ecuación
característica asociada a la relación de recurrencia y resolviéndola.
Casos especiales: Cuando la ecuación característica tiene raíces repetidas, la
solución general tiene una forma ligeramente diferente.
Condiciones iniciales: Las condiciones iniciales son fundamentales para determinar
los valores de las constantes en la solución general.
Principio de Buena Ordenación
Enunciado: Todo subconjunto no vacío de los números naturales tiene un elemento
mínimo.
En otras palabras: Si tienes cualquier conjunto de números naturales (por ejemplo, los
números pares, los números primos, etc.), siempre podrás encontrar un número en ese
conjunto que sea más pequeño que todos los demás.
Intuición: Imagina una recta numérica. Si tomas cualquier trozo de esa recta (es decir,
cualquier conjunto de números naturales), siempre podrás encontrar un punto más a la
izquierda que todos los demás, es decir, el número más pequeño.
Demostración por Inducción (Indirecta)
Aunque el Principio de Buena Ordenación parece intuitivamente claro, podemos
demostrarlo formalmente utilizando el principio de inducción matemática. Sin embargo,
esta demostración será un poco indirecta, ya que asumiremos que el principio de buena
ordenación no se cumple y llegaremos a una contradicción.
Demostración:
1. Supongamos lo contrario: Supongamos que existe un subconjunto no vacío S de
los números naturales que no tiene un elemento mínimo.
2. Definimos un nuevo conjunto: Sea B el conjunto de todos los números naturales
que no están en S.
3. 1 está en B: Si 1 estuviera en S, sería el elemento mínimo de S, lo cual contradice
nuestra suposición. Por lo tanto, 1 debe estar en B.
4. Si k está en B, entonces k+1 también está en B: Si k está en B, significa que k no
está en S. Si k+1 estuviera en S, entonces k+1 sería el elemento mínimo de S (ya
que todos los números menores que k+1 están en B y, por lo tanto, no están en S), lo
cual nuevamente contradice nuestra suposición. Por lo tanto, si k está en B, entonces
k+1 también debe estar en B.
5. Aplicando el principio de inducción: De los puntos 3 y 4, podemos concluir por el
principio de inducción que todos los números naturales están en B.
6. Contradicción: Si todos los números naturales están en B, entonces S está vacío, lo
que contradice nuestra suposición inicial de que S es no vacío.
Conclusión:
Al llegar a una contradicción, hemos demostrado que nuestra suposición inicial (que existe
un subconjunto no vacío de los números naturales sin elemento mínimo) es falsa. Por lo
tanto, el Principio de Buena Ordenación debe ser verdadero.
Relación con el Principio de Inducción
El Principio de Buena Ordenación y el Principio de Inducción están estrechamente
relacionados. De hecho, se puede demostrar que son equivalentes, es decir, cada uno
implica al otro. Esto significa que podemos utilizar uno para demostrar el otro.
¿Por qué es importante el Principio de Buena Ordenación?
Fundamento de las demostraciones: Es una herramienta fundamental para
demostrar propiedades sobre los números naturales.
Algoritmos: Se utiliza en el diseño de algoritmos, especialmente aquellos que
involucran búsqueda o optimización.
Teoría de números: Es esencial para probar muchos resultados en teoría de
números.
En resumen:
El Principio de Buena Ordenación nos asegura que siempre podemos encontrar un elemento
más pequeño en cualquier conjunto no vacío de números naturales. Esta propiedad, aunque
parezca obvia, es fundamental para muchas demostraciones en matemáticas y tiene una
estrecha relación con el principio de inducción.
