Contar con los números de Fibonacci

Otra técnica para contar es establecer alguna recurrencia, un ejemplo muy fácil:

¿Cuántos subconjuntos hay del conjunto {1, 2, 3… n}?
si definimos f(i) como la cantidad de subconjuntos que incluyen números menores o iguales a i podemos decir que f(i+1) = 2f(i) pues por cada conjunto que no contiene a i, se puede formar otro subconjunto igual pero que si lo contiene. Como f(0) = 1 se puede ver que f(n) = 2^n

Además una de las relaciones de recurrencia mas estudiadas es la de los números de Fibonacci, que cumplen con que
f_(i+1) = f(i) + f(i-1) y f(0) = 0, f(1) = 1

Es muy común encontrar esta relación de recurrencia en problemas, por ejemplo:

Un niño baja una escalera de n peldaños dando a veces saltos de 2 peldaños. ¿de cuántas formas distintas puede bajar la escalera?

otra vez supongamos que f(i) es la cantidad de formas distintas que puede el niño bajar hasta el i-esimo peldaño, es muy fácil ver en éste peldaño pudo haber bajado hasta el peldaño anterior y bajar un solo peldaño, o bajar hasta el i-2 y dar un salto. De ahi sabemos que:
f(i) = f(i-1) + f(i-2) y como para el primer peldaño solo hay una forma y para no bajar también solo hay una forma, entonces son exactamente los números de Fibonacci.

Otra aparición muy afortunada de los números de Fibonacci es en caminos:
¿Cuántos caminos hay entre el punto 1 y el punto n en la siguiente figura si solo se puede ir hacia la derecha?

malla de caminos

ir del 1 al n

Otros problemas básicos del estilo son los siguientes:

¿Cuántos subconjuntos hay del conjunto {1,2,3…n} tales que no falten 2 números consecutivos?

¿Cuánto vale la siguiente suma?
\displaystyle \sum_{a+b=n} {a \choose b}

usando la notacion de que {a \choose b} = 0 si a < b o si b < 0

Además usando esas equivalencias se pueden resolver problemas sobre los números de fibonacci, por ejemplo:

Demostrar que f(2n+1) = f(n)^2 + f(n+1)^2

2 comentarios en “Contar con los números de Fibonacci

incluye tu respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s