Archivo de la etiqueta: factorial

Álgebra Superior I: Principio de recursión en los números naturales

Por Guillermo Oswaldo Cota Martínez

Introducción

En esta entrada revisaremos el concepto de recursión en un sentido matemático y revisaremos algunos ejemplos. Probablemente ya hayas escuchado el término, pues verás que es una herramienta útil para definir funciones en términos de las evaluaciones pasadas.

La suma de los primeros n números naturales

Carl Friedrich Gauss fue un matemático alemán del siglo XVIII el cual es uno de los más importantes en distintas disciplinas matemáticas como la teoría de números, la geometría y estadística. Sus aportes son varios en estas y más áreas por lo que nos tomaría varios años de estudio para llegar a muchos de sus resultados. En esta ocasión veremos uno de sus razonamientos más famosos el cual muchos le atribuyen cuando este solo estaba en el colegio cuando aún era niño.

Se dice que el profesor de su clase de matemáticas había castigado a todo el salón haciéndoles sumar los números naturales del $1$ al $100$. La historia dice que no pasó mucho tiempo (y mucho menos del esperado por el profesor) hasta que Gauss llegó con la respuesta «5050». El razonamiento que tuvo fue el siguiente: Para llegar a la suma, pondremos los números del $1$ al $100$ en una lista, y debajo los mismos números pero al revés, es decir, del $100$ al $1$, y notemos que sumando uno a uno los números de las dos listas como los hemos acomodado, queda un mismo número:

$$\begin{array}{cccccc}
&1 & 2 & \dots &99 & 100 \\
+&100 & 99 & \dots &2 & 1 \\
=&101 & 101 & \dots &101 & 101\\
\end{array}$$

De manera que si tenemos los primeros $100$ números, entonces el número resultante de la suma es $101$, de manera que si sumamos estos números, estaríamos sumando $100$ veces el número $101$, pero como hemos sumado dos veces la lista, entonces deberemos dividir entre $2$ para obtener la suma real. Dicho de otra forma: $$ \sum_{i=0}^{100} i = \frac{100(100+1)}{2} .$$
Si recuerdas, esta es la fórmula que probamos en la entrada pasada, pues en el caso general: $$ \sum_{i=0}^{n} i = \frac{n(n+1)}{2} $$

Viendo la suma como recursión

Sigamos pensando en el ejemplo. Para cada $n \in \mathbb{N}$, llamemos $$S_n = \sum_{i=0}^{n} i = \frac{n(n+1)}{2} .$$ Y nota que para cada número natural $n$ se cumple que:

  1. $S_0=0$
  2. Si $n>0$ entonces $S_n = S_{n-1}+n$

Nota ahora que podemos definir a $S_n$ únicamente en términos de la suma de su antecesor con el número. Esto quiere decir que si nos pidieran calcular $S_{51},S_{52},S_{53}$, primero podemos calcular $S_{51}$ sumando todos los números del $0$ al $51$, pero una vez tengamos ese resultado, no es necesario volver a sumar todos los números para $S_{52}$, sino que basta saber quién es $S_{51}$ y sumarle $52$ para obtener el término deseado, lo mismo para el siguiente número de la sucesión $S_{53}=S_{52}+53$. A $S$ se le puede ver como una función $S:\mathbb{N} \rightarrow \mathbb{N} $ donde $S_n$ hace referencia a la función $S$ valuada en $n$, esto quiere decir que $S(n)=S_n$. A esta función se le llamará una función recursiva.

Definición. Una función $\phi: \mathbb{N} \rightarrow \mathbb{N} $ se dice tener la propiedad de recursión si existe $a \in \mathbb{N} $ y una función $f : \mathbb{N} \rightarrow \mathbb{N} $ tal que:

  1. $\phi(0)=a$
  2. Si $n>0$ entonces $\phi(\sigma(n)) = f(\phi(n))$

Veamos esta definición por partes. Retomemos nuestro ejemplo de la suma de los primeros números naturales. La función que es recursiva es $\phi$, esta función debe satisfacer dos condiciones. La primera condición es que se defina a dónde «manda» el $0$, es decir, hace falta saber cómo empezar la definición recursiva, en este caso, se trata de cómo definimos el comportamiento de la función en el primer número del conjunto de los números naturales. La segunda condición se pone más interesante, pues lo que nos dice es que existe una función $f$ tal que la función $\phi$ evaluada en el sucesor de $n$ ($\sigma(n)=n+1$) es la función $f$ valuada en $\phi (n)$. Lo que quiere decir esta oración es que «Si quieres saber quién es $\phi(n+1)$ y ya sabes quién es $\phi (n)$, entonces basta hacerle algo a ese resultado (valuar ese resultado en $f$) para obtener lo querido».

En nuestro ejemplo de la función $S$ (en la definición, esta sería la función $\phi$), la función $f$ es aquella que a cada suma parcial le agrega el número correspondiente. Esto quiere decir que $f$ es la función: $$\begin{align*} f(S(n)) &= S(n)+n \\&= S(n+1)=S(\sigma(n))\end{align*}.$$

Teorema de recursión débil

El siguiente teorema nos garantiza no solo la existencia de funciones recursivas, sino que además nos garantiza que esta es una herramienta para conjuntos distintos al de los números naturales:

Teorema (Recursión Débil): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos una función $f:X\to X$. Entonces existe una única función $\phi:\mathbb{N}\to X$ tal que:

  • $\phi(0)=x_{0}$
  • $\phi(\sigma(n))=f(\phi(n)).$

La demostración de este teorema se verá en el curso de Álgebra Superior II. Y a grandes rasgos nos garantiza el hecho de que las definiciones de las funciones por recursión son matemáticamente válidas. En otras palabras, muestra que somos capaces de definir y usar funciones recursivas.

Algunos ejemplos

Veamos otro ejemplo de este tipo de funciones. Sea $n \in \mathbb{N}$ Definamos $$ n! = n*(n-1)*(n-2)*\dots*2*1.$$ Por ejemplo, $3!=3*2*1=6$. Nota que esta es una función que podemos describir como recursiva al establecer las siguientes condiciones:

  1. $0!=1$
  2. $n!=(n-1)!*n.$

Como veremos en siguientes entradas, esta función llamada factorial se utilizará mucho en conteo y combinatoria, pues nos hablará de el número de formas de combinar un conjunto con algún número de elementos.

El siguiente ejemplo requiere de una pequeña definición:

Definición. Sea $a$ una función. La función $a$ es una sucesión si $a : \mathbb{N} \rightarrow \mathbb{N} $ es una función entre números naturales.

Esta definición nos indica que a las funciones entre números naturales también se les conoce como sucesiones, muchas veces este no será el nombre común al que se refieran a las funciones de $ \mathbb{N} $ en $ \mathbb{N} $ pero si en alguna ocasión ves el término, sabrás a qué se refiere. También es común, al estar hablando de sucesiones, de escribir las evaluaciones de $a$ en cada término $n$ simplemente como $a_n$ es decir $a_n=a(n)$.

Supongamos ahora que tenemos la sucesión definida como $$a_n=5n+2$$. Los cinco primeros términos de esta sucesión son:$$a_0=2$$ $$a_1=7$$ $$a_2=12$$ $$a_3=17$$ $$a_4=22$$ Notemos que podemos escribir esto de forma recursiva, para ello, notemos que únicamente en cada paso estamos sumando un 5, de manera que $$a_{n+1}=a_n+5.$$Adicionalmente, ya sabemos cuánto vale en el $0$, así la siguiente proposición demuestra este hecho:

Proposición $a_n$ puede definirse de forma recursiva como:

  1. $a_0=2$
  2. $a_{n+1}=a_n+5.$

Demostración (por inducción)

Base inductiva. Es claro que $$a_0 = 2 = 0*5+2$$ De manera que se cumple la base de inducción.

Hipótesis inductiva. Supongamos que para $n\geq 0$ se cumple que $$a_n = a_{n-1}+5=5n+2.$$

Paso inductivo. Para demostrar que $$a_{n+1}=a_n+5$$ como dice la proposición, notemos que por definición de la sucesión, $$a_{n+1}=5(n+1)+2=5n+2+5.$$
Ahora, por hipótesis de inducción, $$a_n=5n+2.$$De esta forma, $$a_{n+1}=5(n+1)+2)+5=a_n+5. $$ tal como se quería demostrar.

$\square$

Tarea Moral

  1. Muestra que hay una única función $\phi$ entre número naturales tal que:
    1. $\phi(0)=10$
    2. $\phi(\sigma(n))=2\phi(n)$
  2. Da una definición explícita de la función del inciso anterior.
  3. Da una definición recursiva para las siguientes sucesiones:
    • $a_n=2n$
    • $a_n=2n+1$
    • $a_n=2^n$
    • $a_n=0$

Más adelante…

En esta entrada dimos la idea de lo que significa la recursión en las matemáticas, en la siguiente entrada usaremos esta idea para empezar a definir las operaciones básicas en los números naturales: la suma y el producto.

Entradas relacionadas

  • Ir a Álgebra Superior I
  • Entrada anterior del curso: Problemas de inducción
  • Siguiente entrada del curso: Suma y producto de naturales y sus propiedades

Probabilidad I-Videos: Distribución binomial

Por Aurora Martínez Rivas

Introducción

Esta vez, nos enfocaremos en el estudio de la distribución discreta: asociada a las variables aleatorias que surgen, al tratar con repeticiones de ensayos Bernoulli independientes y que consisten en determinar el número total de éxitos sin importar su orden. Esta distribución se conoce como distribución binomial.

Distribución binomial

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE 104721: “Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM”. Sitio web del proyecto: https://www.matematicasadistancia.com.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  • Demuestra que la función de probabilidad asociada a la distribución binomial es efectivamente una función de probabilidad.
  • Sea $X$ una variable aleatoria tal que $X\sim binomial\left ( n,p\right ) $, demuestra que cuando $k$ pasa de 0 a n.$\ P(X=k)$ primero aumenta monótonamente y luego disminuye monótonamente alcanzando su valor más grande cuando $k$ es el entero más grande menor o igual que $(n+1)p$.
  • Basándote en la demostración del inciso anterior, da una relación recursiva entre las probabilidades asociadas con valores sucesivos de $X$ y con ella encuentra $P(X<4)$ cuando $X\sim binomial\left ( 50,.4\right ) $.
  • Demuestra que si $X$ es una variable aleatoria tal que $X\sim binomial\left ( n,p\right ) $, entonces la función de masa de probabilidad $f_X\left ( k\right ) $ tiene la siguiente propiedad: $f\left ( k-1\right ) f\left ( k+1\right ) \le f\left ( k\right ) ^2$.
  • Sea $X$ una variable aleatoria tal que $X\sim binomial\left ( n,p\right ) $, encuentra la distribución de probabilidad de $n-X$.

Más adelante…

La distribución binomial, es utiliza para la Estimación de probabilidades: asociadas a resultados, en cualquier subconjunto de ensayos que impliquen éxitos o fracasos. Así, como para estimar probabilidades asociadas a juegos de azar.

Por sus aplicaciones en la teoría de probabilidad y estadística, la distribución binomial es probablemente la de uso más frecuente entre las distribuciones discretas,

Entradas relacionadas

Álgebra Superior II: Otras definiciones recursivas en los naturales (exponenciación y factorial)

Por Roberto Manríquez Castillo

Introducción

En las entradas pasadas hemos dado la definición recursiva de la suma y del producto usando el teorema de la recursión débil y probamos las propiedades elementales de estas operaciones usando el principio de inducción.

Continuando con esta línea de pensamiento, en esta entrada definiremos las funciones exponenciales usando las funciones producto; sin embargo, para definir estas funciones, también ocuparemos el teorema de recursión débil. Para ver que no enunciamos en vano la versión fuerte de este teorema, daremos como aplicación la definición de la función factorial, y de la misma forma a como lo hicimos antes, probaremos algunas de sus propiedades haciendo uso del principio de Inducción. Sin embargo, dejaremos algunas de las propiedades como ejercicio para que puedas practicar este tipo de pruebas una vez más.

Exponenciación en los naturales

Desde la educación elemental nos enseñan que «multiplicar es sumar repetidas veces» y que «exponenciar es multiplicar repetidas veces». Formalicemos esta intuición mediante el teorema de recursión.

Definición: Sea $m\in \mathbb{N}$. Definimos $\eta_{m}:\mathbb{N}\longrightarrow\mathbb(N),$ como la función que satisface las siguientes propiedades:

  1. $\eta_{m}(0)=1$
  2. $\eta_m(\sigma(n))=p_{m}(\eta_{m}(n)) $

Así como lo hemos hecho con la definición de producto y de suma, introduciremos la «notación usual» para hablar de esta función. En este caso, definimos $m^n:=\eta_m(n)$.

De este modo, en términos de las notaciones usuales, podemos suplir la propiedad (2) de la definición anterior como $m^{n+1}=m\cdot m^n$.

Las potencias de $0$ y de $1$

Así como lo hicimos con la suma y el producto, analizaremos de forma especial a las funciones $\eta_{0}$ y $\eta_{1}$.

Teorema: Tenemos que $\eta_{0}(0)=1$ y si $n\neq 0$, entonces $\eta_{0}(n)=0$.

La demostración queda como un ejercicio moral. La buena noticia es que hemos trabajado lo suficiente como para no tener que realizar una prueba por inducción. Cuando intentes demostrar esto por tu cuenta, recuerda qué sucede cuando multiplicamos por $0$.

Notemos que así como lo definimos, $0^0$ es $1$ en los números naturales. Sin embargo, como veremos más adelante y como posiblemente lo sabrás ya, la expresión $0^0$ no estará definida en otros sistemas numéricos como los números reales. Al igual que «$0$ es un natural», la definición de $0^0$ frecuentemente varía dependiendo del contexto.

Teorema: Tenemos que $\eta_{1}(n) =1$ para todo $n$ en los naturales.

Demostración. Para este resultado sí procederemos por inducción sobre $n$. Por la parte (1) de la definición de $\eta_{1}$, tenemos que $\eta_{1}(0)=1$. Esta es nuestra base de inducción.

Supongamos que $\eta_{1}(n)=1$. Queda demostrar que $\eta_{1}(\sigma(n))=1.$ Sin embargo esto se sigue ya que por definición, $\eta_{1}(\sigma(n))=1\cdot\eta_{1}(n)=1\cdot 1=1$. Te invitamos a identificar los argumentos que se ocuparon en cada paso

$\square$

La exponencial no conmuta ni asocia

Como la notación que ocupamos para las funciones $\eta_{m}$ no es tan simétrica como la que ocupamos para el producto o para la suma, uno puede esperar que esta operación no sea en general conmutativa. En efecto esto es cierto, solo basta notar que

$0^1\neq1^0$

Así mismo la exponenciación no es en general asociativa, es decir que existen casos en que

$(n^m)^l\neq n^{(m^l)}$

Encontrar un contraejemplo queda como un ejercicio moral.

Le exponenciación y otras operaciones

Cuando estudiamos el producto de números naturales, vimos que esta operación se distribuye sobre la suma, entonces una buena pregunta es preguntarnos qué pasa cuando mezclamos la exponenciación con el producto y la suma. Quedará como ejercicio dar contraejemplos a todas las siguientes proposiciones:

  1. $n^{(l\cdot m)}=n^l\cdot n^l$
  2. $(l+m)^n=l^n+m^n$
  3. $n^{l+m}=n^l+n^m$

Sin embargo, probaremos dos teoremas conocidos usualmente como las leyes de los exponentes. El primero de ellos dice que por la izquierda, la exponenciación sí se distribuye sobre el producto.

Teorema: Si $a,b,n\in\mathbb{N}$, entonces $(a\cdot b)^n=a^n\cdot b^n$.

Demostración. Procedamos por inducción sobre $n$. De la definición de exponencial, tenemos que $(a\cdot b)^0=1=1\cdot 1= a^0\cdot b^0$, por lo que la base de inducción es cierta.

Supongamos que para algún $n$ se tiene que $(a\cdot b)^n=a^n\cdot b^n$ y probemos que $(a\cdot b)^{\sigma(n)}=a^{\sigma(n)}\cdot b^{\sigma(n)}$. Esto es cierto ya que

\begin{align*}
(a\cdot b)^{\sigma(n)}&=(a\cdot b)\cdot (a\cdot b)^n\\
&=(a\cdot b)\cdot (a^n\cdot b^n)\\
&=(a\cdot a^n)\cdot (b\cdot b^n)\\
&=a^{\sigma(n)}\cdot b^{\sigma(n)}
\end{align*}

A diferencia de las entradas anteriores ya ocupamos sin mención las propiedades ya demostradas o la hipótesis de inducción; sin embargo, sería bueno que detallaras las pruebas.

$\square$

Aunque vimos que en general no podemos hablar de que la exponencial se distribuya, sí hay importantes relaciones que notaremos en los siguientes dos teoremas.

Teorema: Si $a,b,n\in\mathbb{N}$, entonces $a^{b+n}=a^b\cdot a^n$

Demostración. De nuevo procederemos por inducción sobre $n$. Si $n=0$, entonces $a^{b+0}=a^b =a ^b \cdot 1=a^b \cdot a^0$, con lo que probamos la base de inducción.

Supongamos entonces que para algún $n$ se tiene que $a^{b+n}=a^b\cdot a^n$, y demostremos el caso para $\sigma(n)$. Sabemos que

\begin{align*}
a^{b+ \sigma(n)}=&a^{\sigma(b+n)}\\
=&a\cdot a^{b+n}\\
=&a\cdot (a^b\cdot a^n)\\
=&a^b\cdot (a \cdot a^n)\\
=&a^b\cdot a^{\sigma(n)}
\end{align*}

Con esto termina la prueba.

$\square$

El siguiente teorema queda como ejercicio de la tarea moral, para que puedas practicar.

Teorema: Si $a,b,n\in\mathbb{N}$, entoces $(a^b)^n=a^{b\cdot n}$.

El factorial

Hasta ahora, sólo hemos ocupado el teorema de recursión débil a la hora de definir las operaciones. A pesar de que antes demostramos que ambas versiones del teorema son equivalentes, la siguiente definición mostrará la naturalidad que tiene el ocupar el teorema de Recursión Fuerte para algunas cosas.

Definición: Se define la función factorial, $f:\mathbb{N}\to \mathbb{N}$, como la única función dada por el teorema de recursión fuerte que cumple que

  • $f(0)=1$
  • $f(\sigma(n))=p_{\sigma(n)}(f(n))$

Usaremos la notación $n!:=f(n)$. Así, la primer parte de la definición dice que $0!=1$ y la segunda dice que $(n+1)!=(n+1)\cdot n!$.

Notemos que en la definición anterior es necesario ocupar el teorema de Recursión Fuerte ya que en cada paso damos una función distinta. En concreto, para dar la definición en $\sigma(n)$ usamos a la función $p_{\sigma(n)}$.

El factorial es una función que jugará un papel importante en varios temas que verás en la facultad. Tiene una fuerte relación con contar cosas, el cual es un tema que posiblemente hayas estudiado en Álgebra Superior II. Aparece al contar las permutaciones de objetos, pero también como parte de la fórmula para los coeficientes binomiales $\binom{n}{k}$. También, lo encontraremos en este curso a la hora de enunciar el teorema de Wilson de teoría de números, pero necesitamos definir más cosas antes de llegar ahí.

Sin embargo, algo que sí podemos hacer ahora es demostrar una propiedad interesante que satisface el factorial.

Proposición: Para todo $n\in \mathbb{N}$, se tiene que $0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+1=(n+1)!$

Demostración. Procederemos por inducción, el caso base es claro ya que $0\cdot 0!+1= 0+1=1!.$

Supongamos que el resultado es cierto para alguna $n$ y con esta suposición probemos que

$0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+(n+1)\cdot(n+1)!+1=(n+2)!$.

Sabemos por nuestra hipótesis de inducción que

\begin{align*}
&0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+(n+1)\cdot(n+1)!+1\\
=&(0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+1)+(n+1)\cdot(n+1)! \\
=&(n+1)!+ (n+1)\cdot(n+1)!\\
=&(n+1)!(1+n+1)\\
=&(n+1)!(n+2)\\
=&(n+2)!
\end{align*}

En la primer igualdad estamos usando la conmutatividad y asociatividad de la suma. En la segunda igualdad, la hipótesis de inducción. Para la tercer igualdad estamos factorizando el término $(n+1)!$. El resto de igualdades se siguen de las definiciones.

$\square$

Resumen de las propiedades de los exponentes

Para finalizar con la entrada, hacemos un repaso de las propiedades que demostramos, posiblemente las conozcas como las leyes de los exponentes

  • Para todo $n$ número natural, se tiene que $n^0=1$
  • Si $n\neq 0$,entonces $0^n=0$
  • Para todo $n$ número natural, se tiene que $n^1=n$
  • Para todo $n$ número natural, se tiene que $1^n=1$
  • Para $l,m,n$ naturales, se tiene que $(l\cdot m)^n=l\n\cdot m^n$
  • Para $l,m,n$ naturales, se tiene que $n^{l+m}=n^l\cdot n^m$
  • Para $l,m,n$ naturales, se tiene que $n^{l\cdot m}=(n^l)^m$

Más adelante…

Con esta entrada, acabamos con las definiciones de operaciones a través de los teoremas de Recursión; sin embargo, no podemos decir que no ocuparemos este teorema en futuras ocasiones, al menos de forma implícita, mucho menos nos olvidaremos del principio de Inducción, el cuál irá siempre adherido al concepto de número natural.

En las siguientes entradas, estudiaremos otro tipo de propiedades de los naturales, relacionadas con el orden y el tamaño que estos tienen. Sin embargo, aún ocuparemos las operaciones que definimos y las relacionaremos; por ejemplo, con el orden que les daremos.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Encuentra los contraejemplos que faltaron en la entrada
  2. Da la demostración de que $0^n=0$, para toda $n$
  3. Prueba que para todos los naturales $a,b,n$, se tiene que $(a^b)^n=a^{b\cdot n}$
  4. El factorial consiste en «multiplicar los primeros enteros». ¿Qué pasa si queremos hacer algo análogo para sumar los primeros enteros? Da una definición recursiva de una función $S(n)=0+1+2+…+n$, ¿por qué en realidad no es necesario dar una definición recursiva de esta función?
  5. Demuestra que si $n,m$ son naturales tales que existe $k\in\mathbb{N}$ tal que $n\cdot k=n^k=m$, entonces $n^m=m^n$. El regreso de esta afirmación es también verdadero, pero para verlo formalmente, necesitamos desarrollar más teoría

Entradas relacionadas

Contando combinaciones

Por Leonardo Ignacio Martínez Sandoval

CombinatoriaLas combinaciones nos permiten contar de cuántas formas podemos elegir algunos objetos de un cierto conjunto de objetos. Comenzamos por una introducción al principio de doble conteo, luego vemos un par de problemas, introducimos la noción de coeficiente binomial y finalmente encontramos una fórmula en términos de factoriales.

Ir a los videos…

Regla del producto, asignaciones y permutaciones

Por Leonardo Ignacio Martínez Sandoval

CombinatoriaLa regla del producto es el segundo principio funamental para contar además de la regla de la suma. Nos permite contar cosas en las cuales tenemos que hacer varias elecciones que luego son compatibles. Como dos consecuencias naturales, tenemos a las asignaciones y a las permutaciones.

Ir a los videos…