Hola a todos, espero que hayan regresado bien de Colima. Algunos problemas pre-problema del día:
Demuestra que:
(a) $F_n^2+F_{n+1}^2=F_{2n+1}$
(b) $F_n^4=F_{n-2}F_{n-1}F_{n+1}F_{n+2}+1$
(c) $\sum_{i,j\geq 0}{\binom{n-i}{j}\binom{n-j}{i}}=F_{2n+2}$
Bonus points a quien encuentre pruebas combinatorias!
Atentos mañana al problema del día!
martes, 1 de febrero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
4 comentarios:
A ver va una prueba combinatoria del primero.
Llamemos q(n) al número de subconjuntos de 1,2,...,n tal que no haya dos elementos consecutivos.
Veamos que q(2n-1)=q^2(n-2)+q^2(n-1).
Para ver esto dividamos en dos casos. Cuando esta el número n y cuando no esta.
Si no esta entonces los números del 1-(n-1) hay q(n-1) formas de elegirlos y tambien los de n+1-2n-1, por lo tanto hay q^2(n-2) opciones en este caso.
Si esta n entonces no esta n-1 ni n+1 por lo tanto para elegir los numeros del 1-(n-2) hay q(n-2) y los del n+2-2n-1 hay q(n-2), por lo tanto en este caso hay q^2(n-2) opciones.
Por lo tanto q(2n-1)^=q^2(n-1)+q^2(n-2), pero en un problema del blog se vio que q(x)=F_x+2, por lo que nos queda lo que queremos.
Bueno, tengo a y b pruebas inductivas
a)p.d. $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$
Notamos que $F_{1}^{2}+F_{2}^{2}=1+1=2=F_{3}$
Notamos que $F_{2}^{2}+2F_{1}F_{2}=1+2=3=F_{4}$
Ahora supondré que hasta cierto k es válido que $F_{k-1}^{2}+2F_{k-2}F_{k-1}=F_{2k-2} y que F_{k-1}^{2}+F_{k}^{2}=F_{2k-1}$ y por inducción demostraré que eso es cierto para toda k.
p.d $F_{2k}=F_{k}^{2}+2F_{k-1}F_{k}\Leftrightarrow F_{2k-1}+F_{2k-2}=F_{k}^{2}+2F_{k}F_{k-1}=F_{k}^{2}+2(F_{k-1}+F_{k-2})F_{k-1}=F_{k}^{2}+F_{k-1}^{2}+F_{k-1}^{2}+2F_{k-1}F_{k-2}$, lo cual por hipótesis de inducción es cierto.
p.d. $F_{2k+1}=F_{k}^{2}+F_{k+1}^{2}\Leftrightarrow F_{2k}+F_{2k-1}=F_{k}^{2}+(F_{k}+F_{k-1})^{2}=F_{k}^{2}+F_{k}^{2}+F_{k-1}^{2}+2F_{k}F_{k-1}$, y esto ya estaba demostrado, entonces quedan comprobadas ambas inducciones.
b)p.d. $F_{k}^{4}=F_{k-2}F_{k-1}F_{k+1}F_{k+2}+1$
Observamos que para k=3 que es el primer caso, funciona. $F_{3}^{4}=2^{4}=16=1\times1\times3\times5+1=F_{k-2}F_{k-1}F_{k+1}F_{k+2}+1$.
Ahora suponemos que es cierto hasta cierto n. p.d. que $F_{k+1}^{4}=F_{k-1}F_{k}F_{k+2}F_{k+3}+1$. Primero notamos que $F_{k+1}^{4}=(F_{k-1}+F_{k})^{4}=F_{k-1}^{4}+4F_{k-1}^{3}F_{k}+6F_{k-1}^{2}F_{k}^{2}+4F_{k-1}F_{k}^{3}+F_{k}^{4}$ y por otro lado observamos que $F_{k-1}F_{k}F_{k+2}F_{k+3}=F_{k-1}F_{k}(F_{k-1}+2F_{k})(2F_{k-1}+3F_{k})=2F_{k-1}^{3}F_{k}+7F_{k-1}^{2}F_{k}^{2}+6F_{k-1}F_{K}^{3}$, ahora nos podemos preocupar por demostrar que:
$F_{k-1}^{4}+4F_{k-1}^{3}F_{k}+6F_{k-1}^{2}F_{k}^{2}+4F_{k-1}F_{k}^{3}+F_{k}^{4}=2F_{k-1}^{3}F_{k}+7F_{k-1}^{2}F_{k}^{2}+6F_{k-1}F_{K}^{3}+1$, eliminando elementos de ambos lados, llegamos a que nos basta mostrar:
$F_{k-1}^{4}+2F_{k-1}^{3}F_{k}+F_{k}^{4}=F_{k-1}^{2}F_{k}^{2}+2F_{k-1}F_{k}^{3}+1=F_{k-1}^{2}(F_{k-1}^{2}+2F_{k-1}F_{k-2}+F_{k-2}^{2})+2F_{k-1}F_{k}^{3}+1$, y eliminando elementos de ambos lados, obtenemos que:
$2F_{k-1}^{3}F_{k}+F_{k}^{4}=F_{k-1}^{2}(2F_{k-1}F_{k-2}+F_{k-2}^{2})+2F_{k-1}F_{k}^{3}+1\Leftrightarrow2$$F_{k-1}^{3}F_{k}+F_{k}^{4}=F_{k-1}^{2}(2F_{k-1}F_{k-2}+F_{k-2}^{2})+2F_{k-1}F_{k}(F_{k-1}^{2}+2F_{k-1}F_{k-2}+F_{k-2}^{2})+1$, y eliminando datos semejantes, tenemos por demostrar que $F_{k}^{4}=2F_{k-1}^{3}F_{k-2}+F_{k-2}^{2}F_{k-1}^{2}+4F_{k-2}F_{k-1}^{2}F_{k}+2F_{k-2}^{2}F_{k-1}F_{k}+1=F_{k-2}F_{k-1}(2F_{k-1}^{2}+F_{k-2}F_{k-1}+4F_{k-1}F_{k}+2F_{k-2}F_{k})+1$$=F_{k-2}F_{k-1}(F_{k-1}^{2}+2F_{k}^{2}+3F_{k-1}F_{k})+1=F_{k-2}F_{k-1}(F_{k+1}^{2}+F_{k}^{2}+F_{k-1}F_{k})+1=F_{k-2}F_{k-1}(F_{k+1}^{2}+F_{k}F_{k+1})+1$$=F_{k-2}F_{k-1}F_{k+1}(F_{k}+F_{k+1})+1=F_{k-2}F_{k-1}F_{k+1}F_{k+2}+1$, con lo cual queda demostrado.
Bien Manuel (asumo que la parte de LaTeX que no se ve está bien) y Bien George (+bonus) (-bonus por no usar LaTeX).
Alguien ha intentado el (c)?
Hint: ¿De cuántas formas se puede llenar un tablero de $1\times n$ con cuadritos y dominos? Si $n$ es impar, entonces se usa una cantidad impar de cuadritos. Así, si $n$ es impar, hay un cuadrito central.
Consideren cuántos dominós quedan a la izquierda y la derecha de este cuadrito central.
Publicar un comentario