Semana 2 - Numeros Naturales e Induccion

Números naturales e inducción

Idea central: en $N = {1, 2, 3, \dots}$ , si una propiedad empieza en $1$ y cada caso la transmite al siguiente, entonces alcanza a todos.

1. Naturales = el conjunto que se construye desde 1

Un conjunto $S \subseteq R$ es inductivo si:

$1 \in S$ (arranque);
$k \in S \Rightarrow k + 1 \in S$ (avance).

$N$ es el menor conjunto inductivo: está contenido en todo conjunto inductivo. Equivale a decir:

H \subseteq N, 1 \in H, k \in H \Rightarrow k + 1 \in H ⟹ H = N .

Esta es la razón lógica de la inducción: el conjunto de índices para los cuales la propiedad es cierta resulta ser un conjunto inductivo.

2. Inducción: entender el salto

Sea $P (n)$ una afirmación sobre $n \in N$ . Definí

H = {n \in N : P (n) es verdadera} .

Para probar $P (n)$ para todo $n$ , no se salta de un caso a “todos”: se prueba que $H$ contiene al 1 y que no puede dejar de contener al siguiente número. Por ser inductivo, $H = N$ .

Paso	Qué probás	Qué significa
Base	$P (1)$	El primer dominó cae.
Paso inductivo	Para un $k$ arbitrario: $P (k) \Rightarrow P (k + 1)$	Cualquier dominó que cae tira al siguiente.
Conclusión	$P (n)$ para todo $n \in N$	No hay un primer natural al que la cadena pueda “cortarse”.

El punto que suele confundir

En el paso inductivo no elegís un $k$ particular ni probás $P (k)$ desde cero. Decís:

“Tomá un $k$ cualquiera. Si $P (k)$ fuera cierta, ¿puedo fabricar $P (k + 1)$ ?”

La hipótesis inductiva (HI), $P (k)$ , es un dato temporal: se usa una vez para demostrar la tesis inductiva (TI), $P (k + 1)$ . La base es lo que hace que ese “si” se active en $k = 1$ ; luego en $k = 2$ , y así sucesivamente.

Antídoto contra el salto: si hubiera un primer $m$ para el que $P (m)$ falla, entonces $m \neq 1$ (por la base), así que $P (m - 1)$ sería cierta. Pero el paso inductivo obligaría a $P (m)$ : contradicción.

3. Plantilla para escribir una demostración

Para demostrar $\sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}$ :

Proposición: $P (n) : \sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}$ .
Base $n = 1$ : $1 = \frac{1 (1 + 1)}{2}$ .
HI: suponé $\sum_{i = 1}^{k} i = \frac{k (k + 1)}{2}$ .
TI:

\sum_{i = 1}^{k + 1} i = \underset{hacer aparecer la HI}{\underset{⏟}{\sum_{i = 1}^{k} i}} + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2} .

Cierre: por inducción, vale para todo $n \in N$ .

Receta mental: escribí la meta con $k + 1$ → separá el término nuevo → reemplazá con HI → simplificá.

4. Cuándo usar cada variante

Variante	Base(s)	Paso
Simple	$P (1)$	$P (k) \Rightarrow P (k + 1)$
Corrida	$P (n_{0})$	$k \geq n_{0} : P (k) \Rightarrow P (k + 1)$
Fuerte	según el inicio	$P (1), \dots, P (k) \Rightarrow P (k + 1)$
Orden 2	dos casos iniciales	$P (k), P (k + 1) \Rightarrow P (k + 2)$

Regla: necesitás tantos casos base como valores previos requiera tu recurrencia. La inducción fuerte no es “más poderosa” que la simple: es una forma conveniente del mismo principio.

5. Recurrencias: Fibonacci y Lucas

Fibonacci = el ejemplo de inducción de orden 2

F_{0} = 0, F_{1} = 1, F_{n + 2} = F_{n + 1} + F_{n} .

Primeros términos: $0, 1, 1, 2, 3, 5, 8, 13, \dots$ .

Como $F_{n + 2}$ depende de dos términos anteriores, para demostrar una identidad sobre Fibonacci necesitás dos bases y, en el paso, las dos HI. Por ejemplo, para una fórmula $P (n)$ :

P (0), P (1), P (k) \land P (k + 1) \Rightarrow P (k + 2) .

Su término general es

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}, φ = \frac{1 + \sqrt{5}}{2}, ψ = \frac{1 - \sqrt{5}}{2} .

Por qué funciona: $φ$ y $ψ$ cumplen $x^{2} = x + 1$ ; por eso sus potencias obedecen la misma recurrencia que Fibonacci. Se verifican $n = 0, 1$ y se concluye por inducción de orden 2.

Cassini:

F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n} (n \geq 1) .

Sucesiones de Lucas: el patrón general

a_{0} = a, a_{1} = b, a_{n + 2} = c a_{n + 1} + d a_{n} .

Si $r \neq s$ son las raíces de $x^{2} - c x - d = 0$ , entonces

a_{n} = α r^{n} + β s^{n}, α = \frac{b - a s}{r - s}, β = \frac{a r - b}{r - s} .

Idea para recordar: misma recurrencia + mismas dos condiciones iniciales = misma sucesión. Fibonacci es el caso $a = 0, b = 1, c = d = 1$ .

Errores frecuentes

Probar la base pero no una transición válida para todo $k$ .
Usar la HI para lo que no dice; si la HI es $P (k)$ , no podés asumir $P (k + 1)$ .
Olvidar que una desigualdad puede empezar a ser cierta recién desde $n_{0}$ .
Aplicar inducción cuando una prueba directa es más corta.

6. Sumatoria y productoria

\sum_{i = 1}^{1} a_{i} = a_{1}, \sum_{i = 1}^{n + 1} a_{i} = \sum_{i = 1}^{n} a_{i} + a_{n + 1} .

\prod_{i = 1}^{1} a_{i} = a_{1}, \prod_{i = 1}^{n + 1} a_{i} = (\prod_{i = 1}^{n} a_{i}) a_{n + 1} .

Las dos maniobras más útiles:

Linealidad: $\sum (a_{i} + b_{i}) = \sum a_{i} + \sum b_{i}$ , $\sum c a_{i} = c \sum a_{i}$ .
Cambiar índice sin cambiar términos: $\sum_{i = 1}^{n} a_{i} = \sum_{j = 0}^{n - 1} a_{j + 1}$ . Revisá siempre inicio, final y término general.

Fórmulas para reconocer:

\sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}, \sum_{i = 0}^{n} q^{i} = {\begin{cases} n + 1, & q = 1, \\ \frac{q^{n + 1} - 1}{q - 1}, & q \neq 1. \end{cases}

7. Factorial y combinatorios

0! = 1, n! = 1 \cdot 2 \dots n, (n + 1)! = (n + 1) n! .

Para $0 \leq k \leq n$ :

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, (\binom{n}{k}) = (\binom{n}{n - k}), (\binom{n + 1}{k}) = (\binom{n}{k}) + (\binom{n}{k - 1}) .

La última identidad construye el triángulo de Tartaglia: bordes $1$ ; cada interior es la suma de los dos de arriba.

Checklist de examen

¿Escribí $P (n)$ con precisión?
¿La base coincide con el inicio real del problema?
¿En la TI hice aparecer exactamente la HI?
¿Mi paso vale para un $k$ arbitrario?
¿Cerré con “por inducción…”?