Inducción Matemática

Entrenamiento Adicional #3 Rumbo a 4ta Etapa

Agosto de 2021

Resumen
La inducción es uno de los métodos de demostración más utilizados, y por lo general funciona para cuando
quieres demostrar una fórmula o una proposición para números, sucesiones, o cuando quieras demostrar algo
“para toda n”. Incluso veremos ejemplos en otras áreas como geometrı́a. Esta semana aprenderemos a utilizar
inducción, para que no tengan excusa de no saber utilizarla.

1. Una analogı́a con dominós

La inducción matemática funciona como si tuvieran una fila de dominós parados en una superficie, y quisieras
tumbar el primero, y con ello provocar que todos caigan. La idea central de la inducción es: Tumbo el primer
dominó manualmente, y reviso que si se tumba el dominó n, siempre se cae el que sigue (el n + 1). Por lo tanto,
si tumbo el primero, el primero tumba al segundo, y el segundo al tercero, y ası́ sucesivamente se tumban todos,
y todos somos felices.

2. Presentando a la Inducción Matemática

La inducción matemática es un método de demostración muy formal, y para que un problema hecho con inducción
esté completo tiene que forzosamente tener estas tres componentes:
Base Inductiva: Es donde intentamos el primer caso (tiene que ser el primero, para poder asegurar que se
tumban todos los casos). Por lo general se utiliza n = 1, pero puede no ser ası́, existirán algunos problemas
en los cuales la base puede ser n = 3, por ejemplo.

Hipótesis de inducción: Aquı́ suponemos que lo que queremos demostrar es cierto. n = n (Simplemente
es volver a decir eso, y creer que funciona)
Paso Inductivo: Aquı́ revisamos el caso siguiente al de la hipótesis, el caso n = n + 1. Y tratamos de
verificar que lleguemos a algo cierto utilizando la base inductiva o la hipótesis de inducción.
Una vez que tengamos esos tres pasos, habremos terminado con la inducción y demostrado lo que querı́amos.
Entonces, revisamos el primer caso (generalmente a manita), y supusimos que habı́a un caso n en alguna parte
de los naturales que cumplı́a, luego revisamos que el caso siguiente al n (el n + 1) también cumple, siempre y
cuando su anterior se cumpla. Entonces, si el caso de nuestra base inductiva se cumple, podemos asegurar que se
cumplen todos. ¡Woohoo!
Ejemplo 1.
Demuestra que el producto de dos números enteros positivos consecutivos siempre es par.

Solución.
Comencemos con la Base Inductiva, que es nuestro primer caso:

BI : (1)(2) = 2

Olimpiada Mexicana de Matemáticas en Baja California 2021 1

[Link]
Una vez viendo que nuestra base inductiva cumple con lo que queremos proponer, pasamos a la Hipótesis de
Inducción, que es la proposición para n:
HI : (n)(n + 1) = 2k
Y la suponemos como cierta, para ir al Paso Inductivo, donde queremos demostrar lo siguiente:

PI : (n + 1)(n + 2) = 2q

Vamos a desarrollar el paso inductivo:

n2 + n + 2n + 2 = 2q
Pero ya sabemos, por la Hipótesis de inducción, que n2 + n = 2k, entonces vamos a sustituir eso en lo que ya
tenemos:
2k + 2n + 2 = 2q
Y entonces concluimos que: si el caso n nos da par, el caso siguiente (n + 1) siempre nos da par. Entonces el
primer caso nos da el segundo, y el segundo el tercero, y ası́ sucesivamente se tumban todos los casos. 

3. Agregados culturales
1. Contrario a lo que mucha gente piensa, se escribe dominós y no dominoes cuando se refiere al plural de la
palabra dominó.
2. Los métodos de demostración que más utilizamos son: Demostración directa, contradicción, contrapositiva,
inducción.
3. Si intentas demostrar lo que dice un problema en un examen con inducción (que esa sea toda tu solución),
y no tienes los tres pasos completos tendrás 0 puntos. Ası́ que te recomiendo que te acostumbres a usarlos
y escribirlos.
4. Habı́a una olı́mpica en Baja California que la mayorı́a de sus problemas los intentaba con inducción. Era su
tema favorito.
5. Se ha comprobado que las vacas son capaces de demostrar emociones, e incluso aumenta su ritmo cardı́aco
cuando se les desafı́a a abrir una puerta para conseguir comida. Algunas brincan de la emoción al lograrlo
(como tú cuando resuelves ese problema que tenı́as pendiente).

4. Lista de problemas
4.1. Básicos
Demuestra las siguientes proposiciones para todos los enteros positivos n:
n(n+1)
1. 1 + 2 + 3 + · · · + n = 2 (Sumatoria de Gauss)
2. 1 + 3 + 5 + · · · + (2n − 1) = n2
(n)(n+1)(2n+1)
3. 12 + 22 + 32 + · · · + n2 = 6
 2
(n)(n+1)
4. 13 + 23 + 33 + · · · + n3 = 2 (Teorema de Nicómaco)
1 1 1 1 n
5. 1·2 + 2·3 + 3·4 + ··· + n(n+1) = n+1

r n −1
6. 1 + r + r 2 + r 3 + · · · + r n−1 = r −1

Olimpiada Mexicana de Matemáticas en Baja California 2021 2

[Link]
 7. 6|n3 + 5n
8. 3|n3 − n + 3

9. 4|5n − 1
10. 11|23n − 1
11. x − y |x n − y n
12. 2n ≤ 3n

4.2. ¡Fibonaccis!
Les presento a la famosa sucesión de Fibonacci. Famosa aunque muy poca gente la entiende y sabe utilizarla,
aunque los que la conocemos a fondo, sabemos que está en todas partes... sı́, en todas partes, en serio.
La sucesión de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, 21, ...) se define por F0 = 0, F1 = 1, Fn+2 = Fn + Fn+1 ∀ n ≥ 0.
Utilizando estos números y la definición de la sucesión, hay que demostrar lo siguiente. ¿Qué, pensaban que sólo
se las iba a presentar? ¡Al ataque!

1. F1 + F2 + · · · + Fn = Fn+2 − 1
2. F12 + F22 + · · · + Fn2 = Fn Fn+1

3. Fn = n−1 + n−2 + n−3

0 1 2 + ···
2
4. Fn−1 + Fn2 = F2n−1

4.3. Tutifrutti de Inducción

1. Demuestra que n = 4, 5, 6, ... implica 2n < n!
1 1
2. Sea α un número real tal que α + α ∈ Z. Prueba que: αn + αn ∈ Z para todo n ∈ Z
3. Demuestra que para todo n ∈ N (1 + x)n ≥ 1 + nx si x ≥ −1 (Desigualdad de Bernoulli)

4. Sea S un conjunto con n elementos. Demuestra que el conjunto de todos los subconjuntos de S tiene 2n
elementos.
5. Demuestra que para todo n ∈ N:
       
n n n n
+ + + ··· + = 2n
0 1 2 n

6. Un saltamontes está sentado en la primera casilla de una fila. Cada minuto brinca a la derecha con saltos
de uno o dos cuadritos. ¿De cuántas maneras puede llegar a la n-ésima casilla?

7. “Las torres de Hanoi” es un rompecabezas con 3 clavos y 7 aros todos de diferentes tamaños. Inicialmente,
todos los aros están en el mismo clavo ordenados por tamaños (el más chico arriba). El procedimiento es
quitar el aro de hasta arriba de algún clavo y colocarlo en otro. No es permitido tener un aro más grande
sobre uno más chico. ¿Es posible llegar a tener todos los aros en otro clavo con este procedimiento? ¿Cuál
es el mı́nimo número de operaciones necesarias para resolver el rompecabezas? Encuentra una fórmula y
demuéstrala.
8. N rectas dividen al plano en diferentes secciones. Encuentra el número de secciones formadas si cualquier
par de rectas se intersecan y no hay tres que pasen por un mismo punto.

Olimpiada Mexicana de Matemáticas en Baja California 2021 3

[Link]
 9. Prueba que la suma de ángulos internos de cualquier n-ágono es 180(n − 2).
10. Todas las carreteras de Sikinia son de un sentido. Cada par de ciudades esta conectada por exactamente
una carretera. Muestra que existe una ciudad puede ser accesada por cada una de las otras ciudades ya sea
de manera directa, o vı́a a lo más otra ciudad.
11. Prueba que todos los enteros positivos impares se pueden escribir en la forma a0 + a1 · 2 + a · 22 + · · · + an · 2n ,
para algún entero positivo n y cada ai = ±1. (por ejemplo, 11 = 1 − 2 + 4 + 8).
12. (Binomio de Newton) Sean a y b números arbitrarios y sea n ∈ N, entonces:
         
n n n n n−1 1 n n−r r n 1 n−1 n n
(a + b) = a + a b + ··· + a b + ··· + a b + b
0 1 r n−1 n

4.4. Problemas más Jarcors

1. Sea An el conjunto con los elementos {1, 2, 3, ... , n}. Para cada subconjunto no vacı́o de An , es decir, con
al menos un elemento, se calcula el producto de sus elementos, y se obtiene su recı́proco. Sea Sn la suma
de todos estos recı́procos. Encuentra S2013 .
2. Una sucesión {an } de números reales está definida por a0 = 1, a1 = 2015, y para todo entero n ≥ 1 como:

n−1 n−2
an+1 = an − 2 an−1
n+1 n +n
Calcula el valor de:
a1 a2 a3 a4 a2013 a2014
− + − + ··· + −
a2 a3 a4 a5 a2014 a2015
Pn
3. k=1 k · k! = (n + 1)! − 1
4. 2304|72n − 48n − 1
5. S es un conjunto con n elementos. Prueba que la cantidad de subconjuntos de ese conjunto es 2n .

6. Determina la cantidad máxima de regiones en las cuales puede partirse un plano con n lineas.
7.

Olimpiada Mexicana de Matemáticas en Baja California 2021 4

[Link]