tag:blogger.com,1999:blog-444408592833092365.post1704548777645529141..comments2023-06-29T04:02:58.043-06:00Comments on México rumbo a la IMO: Algunos problemas de FibonaccisDavid (sirio11)http://www.blogger.com/profile/13765612869477578855noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-444408592833092365.post-49686160694946280012011-02-03T11:19:40.499-06:002011-02-03T11:19:40.499-06:00Bien Manuel (asumo que la parte de LaTeX que no se...Bien Manuel (asumo que la parte de LaTeX que no se ve está bien) y Bien George (+bonus) (-bonus por no usar LaTeX).<br /><br />Alguien ha intentado el (c)?<br /><br />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.<br /><br />Consideren cuántos dominós quedan a la izquierda y la derecha de este cuadrito central.Leohttps://www.blogger.com/profile/12331932800328151846noreply@blogger.comtag:blogger.com,1999:blog-444408592833092365.post-62812950325526165032011-02-02T17:40:09.450-06:002011-02-02T17:40:09.450-06:00b)p.d. $F_{k}^{4}=F_{k-2}F_{k-1}F_{k+1}F_{k+2}+1$
...b)p.d. $F_{k}^{4}=F_{k-2}F_{k-1}F_{k+1}F_{k+2}+1$<br /><br />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$.<br /><br />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:<br /><br />$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:<br /><br />$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:<br /><br />$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.Manuel Alejandrohttps://www.blogger.com/profile/17984744396551043970noreply@blogger.comtag:blogger.com,1999:blog-444408592833092365.post-6630636964454486622011-02-02T16:38:48.390-06:002011-02-02T16:38:48.390-06:00Bueno, tengo a y b pruebas inductivas
a)p.d. $F_{...Bueno, tengo a y b pruebas inductivas<br /><br />a)p.d. $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$<br /><br />Notamos que $F_{1}^{2}+F_{2}^{2}=1+1=2=F_{3}$<br /><br />Notamos que $F_{2}^{2}+2F_{1}F_{2}=1+2=3=F_{4}$<br /><br />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.<br /><br />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.<br /><br />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.Manuel Alejandrohttps://www.blogger.com/profile/17984744396551043970noreply@blogger.comtag:blogger.com,1999:blog-444408592833092365.post-13235409588550794062011-02-01T21:07:45.668-06:002011-02-01T21:07:45.668-06:00A ver va una prueba combinatoria del primero.
Lla...A ver va una prueba combinatoria del primero.<br /><br />Llamemos q(n) al número de subconjuntos de 1,2,...,n tal que no haya dos elementos consecutivos.<br /><br />Veamos que q(2n-1)=q^2(n-2)+q^2(n-1).<br /><br />Para ver esto dividamos en dos casos. Cuando esta el número n y cuando no esta. <br /><br />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.<br /><br />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.<br /><br />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.Georgeshttps://www.blogger.com/profile/01952800395162229443noreply@blogger.com