Archivo de la etiqueta: factorial

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

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

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  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

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.

Entradas relacionadas

Contando combinaciones

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

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…