Demuestra que para todo entero positivo $n$:
$$n! = \prod_{i=1}^n mcm\{1,2,\ldots,\left\lfloor\frac{n}{i}\right\rfloor\}.$$
Donde $mcm$ es el mínimo común múltiplo y $\lfloor x\rfloor$ es el mayor entero $\leq x$.
viernes, 11 de febrero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
11 comentarios:
Con $n=1$, obviamente se cumple. Supongamos que se cumple para cierto $n$. Demostraremos que se cumple para $n+1$. Tenemos que $\left\lfloor \frac{n+1}{d}\right\rfloor = \left\lfloor \frac{n}{d}\right\rfloor+1$ si y solo si $d|n+1$. Si no lo divide, entonces $\left\lfloor \frac{n+1}{d}\right\rfloor = \left\lfloor \frac{n}{d}\right\rfloor$. Entonces
$$\frac{\prod_{i=1}^{n+1} mcm\{1,2,\ldots,\left\lfloor\frac{n+1}{i}\right\rfloor\}}{\prod_{i=1}^n mcm\{1,2,\ldots,\left\lfloor\frac{n}{i}\right\rfloor\}}$$
$$= \prod_{d|n+1;d\neq n+1}\frac{mcm\{1,2,\ldots,\frac{n+1}{d}\}}{mcm\{1,2,\ldots,\frac{n+1}{d}-1\}}$$
$$= \prod_{d|n+1;d\neq 1}\frac{mcm\{1,2,\ldots,d\}}{mcm\{1,2,\ldots,d-1\}}$$
Si $d\neq p^{\alpha}$ entonces todos los divisores de $d$ ya estan en $mcm\{1,2,\ldots,d-1\}$ por lo que $mcm\{1,2,\ldots,d-1\}=mcm\{1,2,\ldots,d\}$. Si $d=p^{\alpha}$ entonces $mcm\{1,2,\ldots,d-1\} \cdot p=mcm\{1,2,\ldots,d\}$ Porlotanto
$$\prod_{d|n+1;d\neq 1}\frac{mcm\{1,2,\ldots,d\}}{mcm\{1,2,\ldots,d-1\}}=$$
$$= \prod_{d|n+1;d=p^{\alpha};d\neq 1} p = n+1$$
Porlotanto
$$\prod_{i=1}^{n+1} mcm\{1,2,\ldots,\left\lfloor\frac{n+1}{i}\right\rfloor\}=$$
$$\left(n+1\right) \cdot \prod_{i=1}^{n} mcm\{1,2,\ldots,\left\lfloor\frac{n}{i}\right\rfloor\}=$$
$$\left(n+1\right) \cdot n!=\left(n+1\right)!$$
Esta suave tu demostración Diego. Muy bien.
Vemos para cada primo p que la cantidad de factores de este es la misma en los dos lados:
Del lado derecho, es conocido que es la suma de $\lfloor \frac{n}{p^i} \rfloor$, $i \ge 1$
del lado izquierdo,cada factor tiene como factor p la mas grande potencia de p menor o igual a $\lfloor frac{n}{i} \rfloor$, es decir
$log_p \lfloor frac{n}{i} \rfloor$
Ahora usare la siguiente notacion: [p]=1 si la proposicion p es cierta y [p]=0 si es falsa.
Entonces la primera suma, la que dice del lado derecho, es suma i=1 a inf de Suma de k=1 a inf de [k<=n/p^i]. Osea cuantos enteros son menores o iguales a n/p^i= su funcion piso.
Dela lado derecho nos queda la Suma de k=1 a inf (o a n , pero si k>n, los terminos se vuelven cero) de parte entera de
$log_p \lfloor frac{n}{i} \rfloor$, pero esa parte entera es igual a Suma de i=1 a inf de [p^i<=parte ent de n/k]= [p^i<=n/k], por que es la cantidad de potencias de p que son menores o iguales a n/k. Entonces si nos fijamos [k<=n/p^i]=[k*p^i<=n]=[p^i<=n/k], o sea que los sumandos en ambas sumas son los mismos, solo que en una suma los contadores de una estan adentro y en otra fuera, pero cambiarlos no afecta pues no se utiliza ninguna variable hasta adentro de la segunda suma, entonces ambas sumas son iguales y la cantidad de factores p de ambos lados son los mismos, entonces las mismas potencias de p dividen a cada lado, entonces son el mismo numero.
donde dice $fracni$ es $\frac{n}{i}$
Muy bien Flavio. La idea que usas es conocida como cambiar el orden de los sumandos ya que tradujiste el problema a una doble suma en $i$ y $k$ y luego la cambias a una doble suma en $k$ e $i$. Es una técnica con muchos usos en teoría de números.
Probémoslo por inducción. Es claro que n=1 funciona. Ahora analicemos las siguientes propiedades:
$\lfloor \dfrac{n+1}{i} \rfloor = \lfloor \dfrac{n}{i} \rfloor \Leftrightarrow i\nmid n+1$ por lo que $mcm\{1, 2, ..., \lfloor \dfrac{n+1}{i} \rfloor\} = mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\} \Leftrightarrow i\nmid n+1$
Veamos qué pasa si para una $n$ entera en las siguientes sircunstancias:
$n+1=p^{\alpha}$ para algún $p$ primo y un $\alpha$ entero positivo. De aquí que en $\{1, 2, ..., n\}$ está incluido a $p^{\alpha-1}$ por lo tanto, $p^{\alpha-1}|mcm\{1, 2, ..., n\}$ sin embargo, $p^{\alpha}\nmid mcm\{1, 2, ..., n\}$ por lo que $p^{\alpha}||p\cdot mcm\{1, 2, ..., n\}$ y entonces $mcm\{1, 2, ..., n+1\}=p\cdot mcm\{1, 2, ..., n\}$.
De manera similar, si $n+1=\Pi_{i=1}^{k} p_{i}^{\alpha_{i}}$ para una $k$ entera mayor a uno, entonces tenemos que como para cada $i$, se tiene que $p_{i}^{\alpha_{i}}|mcm\{1, 2, ..., n\}$ entonces $mcm\{1, 2, ..., n\}=mcm\{1, 2, ..., n+1\}$.
Ahora supongamos que funciona hasta cierta $n$, veamos que para $n+1$ también funciona. Para esto, veamos que en $\Pi_{i=1}^{n+1} mcm\{1, 2, ..., \lfloor \dfrac{n+1}{i} \rfloor\}$ y en $\Pi_{i=1}^{n} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}$ hay valores en común, como ya habíamos visto, son iguales los términos en que $i\nmid n+1$ por lo que tenemos que $\dfrac{\Pi_{i=1}^{n+1} mcm\{1, 2, ..., \lfloor \dfrac{n+1}{i} \rfloor\}}{\Pi_{i|n+1}^{n+1} mcm\{1, 2, ..., \dfrac{n+1}{i} \}}=\dfrac{\Pi_{i=1}^{n} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}}{\Pi_{i|n+1}^{n} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}}$ por lo que, si demostramos que $\Pi_{i|n+1}^{n+1} mcm\{1, 2, ..., \dfrac{n+1}{i} \}=(n+1)\cdot\Pi_{i|n+1}^{l} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}$ siendo $l$ el divisor más grande de $n+1$ distinto de $n+1$, por nuestra hipótesis de inducción, habremos acabado, y para demostrar esto, podemos dividirlo en dos casos:
Caso A) $n+1=p^{\alpha}$ para $p$ primo y $\alpha$ un entero positivo. Para este caso, sabemos que $i$ toma valores como $p^{\beta}$ para $\alpha\geq\beta\geq 0$ y como para cada valor de $i$ tenemos la propiedad que analizamos hace rato, la cual nos dice que$mcm\{1, 2, ..., p^{\beta}\}=p\cdot mcm\{1, 2, ..., p^{\beta}-1\}$ ya que $i|n+1$ (lo que hace que $\lfloor \dfrac{n+1}{i} \rfloor \neq \lfloor \dfrac{n}{i} \rfloor$ y entonces sea menor en uno). Por lo que $\Pi_{i|n+1}^{n+1} mcm\{1, 2, ..., \dfrac{n+1}{i} \}=\Pi_{i|n+1}^{p^{\alpha-1}} p\cdot mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}=p^{\alpha}\cdot\Pi_{i|n+1}^{p^{\alpha-1}} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}$ y como $n+1=p^{\alpha}$ acabamos este caso.
Caso B) $n+1=\Pi_{i=1}^{k} p_{i}^{\alpha_{i}}$ para $p_{i}$ primo y $\alpha_{i}$ entero positivo y con $k$ entro mayor a $1$. Como vemos, si en $\Pi_{i|n+1}^{n+1} mcm\{1, 2, ..., \dfrac{n+1}{i} \}=(n+1)\cdot\Pi_{i|n+1}^{l} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}$, al dividir a $n+1$ entre $i$ obtenemos un número compuesto entonces, nos da el mismo valor en el mínimo común múltiplo, como ya habíamos visto, así que podemos reducir este caso a cuando $i$ es de la forma $\dfrac{n+1}{p_{x}^{y}}$ de modo que se reduce a probar que $\Pi_{i=1}^{k} (\Pi_{j}^{\alpha_{i}} mcm\{1, 2, ..., p_{i}^{j} \})= \Pi_{i=1}^{k} p_{i}^{\alpha_{i}} \cdot\Pi_{i=1}^{k} (\Pi_{j}^{\alpha_{i}} mcm\{1, 2, ..., p_{i}^{j}-1 \})$ y como sabemos, $mcm\{1, 2, ..., p_{i}^{j}\}=p_{i}\cdot mcm\{1, 2, ..., p_{i}^{j}-1\}$ por lo que lo que queremos probar se reduce a propar que $\Pi_{i=1}^{k} (p_{i}^{\alpha_{i}})= \Pi_{i=1}^{k} p_{i}^{\alpha_{i}}$ lo cual es verdad, por lo que usando nuestra hipótesis de inducción de que $\Pi_{i=1}^{n} mcm\{1, 2, ..., \lfloor \dfrac{n}{i} \rfloor\}=n!$ obtenemos que $\Pi_{i=1}^{n+1} mcm\{1, 2, ..., \lfloor \dfrac{n+1}{i} \rfloor\}=(n+1)!$ y acabamos.
Empezaremos detallando unos hechos importantes.
En primer lugar, tenemos que ⌊(n+1)/k⌋=⌊n/k⌋+1 si y sólo si k|n+1, de lo contrario ⌊(n+1)/k⌋=⌊n/k⌋. (1)
Por otro lado, mcm[1,2,3,…,n] es igual al producto de las máximas potencias de primos antes de n, es decir, mcm[1,2,3,…,n] = 2^(α_1 )•3^(α_2 )•5^(α_3 )•…•P_k^(α_k )•… , donde P_k es el k-ésimo primo en la sucesión de primos y los α_i, con i=1,2,3,… son enteros no negativos tales que P_i^(α_i )≤n≤P_(i+1)^(α_(i+1) ) para toda i. De aquí podemos ver que mcm[1,2,3,…,p^a]= 2^(α_1 )•3^(α_2 )•5^(α_3 )•…•p^a=p(2^(α_1 )•3^(α_2 )•5^(α_3 )•…•p^(a-1)) = p mcm[1,2,3,…,p^a-1] con p primo y a un entero no negativo. (2)
De aquí también es fácil ver que si n no es potencia de un primo, mcm[1,2,3,…,n] = mcm[1,2,3,…,n-1] con n≥2. (3)
Lo haremos por inducción sobre n. Es fácil verificar que es cierto para n=1. Ahora, supongamos que para algún n se cumple el problema. Sea n+1=P_1^(α_1 ) P_2^(α_2 )…P_k^(α_k ) su descomposición en factores primos. Entonces, ∏_(i=1)^(n+1)▒mcm [1,2,…,⌊(n+1)/i⌋ ]=∏_(k|n+1)▒mcm[1,2,…,⌊(n+1)/k⌋ ] ∏_(k∤n+1,1≤k≤n+1)▒mcm[1,2,…,⌊(n+1)/k⌋ ] =∏_(k|n+1)▒mcm[1,2,…,⌊(n+1)/k⌋ ]·∏_(k∤n+1)▒mcm[1,2,…,⌊n/k⌋ ] (por (1) )=
∏_(k=p^a,k|n+1)▒mcm[1,2,…,k]·∏_(k≠p^a,k|n+1)▒mcm[1,2,…,k]·∏_(k∤n+1)▒mcm[1,2,…,⌊n/k⌋]=∏_(k=P_i^(a_j),k|n+1)▒mcm[1,2,…,k]·∏_(k≠p^a,k|n+1)▒mcm[1,2,…,k]·∏_(k∤n+1)▒mcm[1,2,…,⌊n/k⌋ ]=P_1^(α_1 )·P_2^(α_2 )·…·P_k^(α_k )·∏_(k=P_i^(a_j ),k|n+1)▒mcm[1,2,…,k-1]·∏_(k≠p^a,k|n+1)▒mcm[1,2,…,k-1]·∏_(k∤n+1,1≤k≤n)▒mcm[1,2,…,⌊n/k⌋ ] (por (2) y (3))=(n+1)·∏_(k|n+1,k≠n+1)▒mcm[1,2,…,⌊n/k⌋ ] ·∏_(k∤n+1,1≤k≤n)▒mcm[1,2,…,⌊n/k⌋ ] (por (1) )=(n+1) ∏_(i=1)^n▒mcm[1,2,…,⌊n/i⌋ ]=(n+1)(n!)(por hipótesis de inducción)=(n+1)!
∎
Nota: ∏_(i=1)^k▒a_i=a_1·a_2·…·a_k
Vemos que para n=1 se cumple, entonces tomaremos este caso como hipótesis de inducción y supondremos que se cumple hasta cierta n, queremos demostrar que se cumple para n+1. Basicamente queremos ver que el siguiente número de la multiplicatoria es el anterior por n+1
Sabemos que (n,n+1)=1 porque son números consecutivos, Definamos f(i) a el mcm de $1,2\dots\left\lfloor\frac{n}{i}\right\rfloor$ y g(i) el mcm de $1,2,\dots\left\lfloor\frac{n+1}{i}\right\rfloor$
Veamos que si n+1 es primo entonces g(i) = f(i) ya que como i no divide a n+1 por ser primo entonces el piso es igual que en el caso del numero anterior que es n. El único i que cambiaría sería g(1) porque 1|n+1, y como ningún numero menor a n+1 lo divide el mcm será el del caso anterior por n+1.
Ahora, generalizando el caso n+1=primo, vemos las siguientes cosas
Si i no divide a n+1 entonces g(i) = f(i) por lo tanto no los consideramos
Si i|n+1, primero sabemos que no divide a n (porque n y n+1 son primos relativos) por lo tanto f(i) no es igual a g(i), pero si pueden valer lo mismo.
Por ejemplo en el caso en que $\frac{n+1}{i}=(p_j^x)(p_s^y)$ con $p_j^x$ y $p_s^y$ divisores de n+1
Tenemos un número más dentro de [] pero sabemos que $p_j^x$ es menor que $(p_j^x)(p_s^y)$ análogamente para $p_s^y$ por lo tanto el mcm del caso anterior será igual que este caso porque ambos factores (primos relativos entre sí) lo dividen
Entonces los únicos mcm que cambian son aquellos en que $\frac{n+1}{i}=p_j^x$ por que aumentan el exponente de ese determinado primo, por lo tanto el valor de g(i) será igual a f(i) multiplicado por $p_j$ y si sabemos que
$n+1=(p_1^k^1)(p_2^k^2)\dots(p_r^k^r)$
El total de veces que se multiplica $p_j$ es r veces, con $\frac{n+1}{i}= p_j, p_j^2, p_j^3, \dots ,p_j^r$
Por lo tanto queda demostrado que el caso de n+1 es igual al caso de n por n+1 que es (n+1)!
Primero hay que notar que d divide a n+1 sii ⌊((n+1)/d)⌋=⌊n/d⌋+1, en caso contrario ⌊((n+1)/d)⌋=⌊n/d⌋, tambien veamos si d no es potencia de un primo mcm[1,2,…,d])=mcm [1,2,…,⌊d-1⌋], y si d es potencia de un primo P, entonces mcm[1,2,…,⌊d ])=P(mcm [1,2,…,d-1])
Lo hare por induccion
para n=1 es claro.Suponemos para un n fijo
veamos que (∏_(i=1)^(n+1)#mcm[1,2,…,⌊(n+1)/i⌋])/ (∏_(i=1)^(n)#mcm [1,2,…,⌊(n)/i⌋])=(∏_(d/n+1, d distinto de n+1)#mcm[1,2,…,⌊(n+1)/d⌋])/ (∏_(d/n+1, d distinto de n+1)#mcm [1,2,…,⌊((n+1)/d)-1⌋])=∏_(d/n+1, d distinto de n+1)#(mcm[1,2,…,⌊(n+1)/d⌋])/(mcm [1,2,…,⌊((n+1)/d)-1⌋ ])=∏_(d/n+1, d distinto de 1)#(mcm[1,2,…,d])/ (mcm [1,2,…,d-1])=∏_(d/n+1, d=P^a,d distinto de 1)#P=n+1=, entonces
∏_(i=1)^(n+1)#mcm[1,2,…,⌊(n+1)/i⌋]=(n+1)(∏_(i=1)^(n)#mcm [1,2,…,⌊(n)/i⌋])=(n+1)(n!)=(n+1)!, concluyendo que se cumple para todo n natural.
nota: ∏_(i=1)^k#a_i=a_1·a_2·…·a_k
Me salio el problema, pero no tengo mucho tiempo para escribirlo bien, y creo que esta medio dificil escribirlo en la compu, pero la idea es la siguiente, para cada primo meno a p, me fijo en la mayor potencia que divida al lado derecho y al lado izquierdo, y quiero que sea el mismo, para ello me fijo que del lado derecho sera p.e.(parte entera) de n/p + p.e. n/(p^2)+ ..... y asi hasta llegar a la mayor potencia de p menor a n.
contar el lado derecho es más complicado,
para simplificar escribo
$ n= a_k[p^k]+ a_{k-1}[p^{k-1}]+....+a_0 $
y defino:
$ n_i=a_k[p^{k-i}]+ a_{k-1}[p^{k-i-1}]+...+a_i $
para $ 0<i<k+1 $
luego me fijo en que:
$n/(n_j+1) < p^j <o= n/(n_j)$ para toda j
viendo esto y fijandonos en que la mayor potencia de p que divide a $ mcm\{1,2,\ldots,\left\lfloor\frac{n}{i}\right\rfloor\} $ es k si $ p^k < \left\lfloor\frac{n}{i}\right\rfloor\ < p^{k+1} $ podemos sacar una formula de suma de n_i ´s que despusde una s modificaciones nos queda igual a la de n!.
Esa es basicmente la idea de mi solución.
Muy bien Jorge, Enrique, Karina y Angel.
Esta bien tu ataque Daniel. Flavio arriba tiene una solucion con esas ideas.
Publicar un comentario