DEF:

Sea $p(n)$ una proposición sobre los números naturales:

Si se cumple

• Caso base: $p(1)$ V

• Paso inductivo: $\forall h \in \N$

  $p(1) V,\space p(2) V,...,\space P(h) V \implies p(h+1) \space V$.

  Es lo mismo que decir: $p(k)\space V, \quad 1≤ k ≤ h \implies p(h+1) V$

Entonces $p(n)$ es V, $\forall n \in \N$

Principio de inducción completa corrido

Sea $n_0 \in \Z$, y sea $p(n)$, $n ≥ n_0$, una proposición enunciada sobre $Z_{≥n_0}$.

Entonces si se cumple:

1. Caso base: $p(n_0)$ V

2. Paso inductivo $\forall h ≥ n_0$

   $p(k) V,\space n_0 ≤ k ≤ h \implies p(h+1)$ V

Entonces $p(n)$ es V $\forall n ≥ n_0$.

Combinatoria

Cardinal de un conjunto

1. DEF:

   Sea $A$ un conjunto, $\#A$ = cantidad de elementos que tiene $A$.

   Ejemplos:

   • $A = \{1, 2, 3\} ⇒ \#A = 3$
   • $A = {\emptyset} ⇒ \#A = 0$
   • $A = \N ⇒ \#A = \infin$

   Si $A$ tiene finitos elementos decimos que $A$ es un conjunto finito.

   Obs: Sea $A$ un conjunto finito, entonces

   $\#A = \N_0$

Observación: Sean $A$, $B$ conjuntos finitos

1. Inclusión: Si $B \subseteq A$, entonces $\#B ≤ \#A$
2. Unión:
   • Si $A$ y $B$ son disjuntos, entonces $\#(A\cup B) = \#A + \#B$
   • Si $A$ y $B$ son conjuntos finitos cualesquiera, entonces $\#(A\cup B) = \#A + \#B - \#(A\cap B)$
3. Complemento: Supongamos $A \subseteq U$ conjunto referencial finito: $\#A^C = \#U - \#A$