jump to navigation

Contar con los números de Fibonacci Julio 26, 2008

Posted by Álvaro in combinatoria, introductorios, trucos, varios.
Tags: , , , , ,
2 comments

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?
 (más…)

La Inducción, el buen orden y el descenso infinito Noviembre 30, 2007

Posted by Álvaro in teoremas, trucos.
Tags:
1 comment so far

Una de las cosas mas importantes en matemáticas es el principio de inducción. Sea A(n) una propiedad de algunos números de modo que ésta propiedad se “contagie” de un número al siguiente. Si el cero cumple esta propiedad, entonces todos los naturales cumplen.

Puesto como formula…
\displaystyle \textrm{Si } A(0) \textrm{ y } A(n) \Rightarrow A(n+1),\; \textrm{entonces} \; \forall i \in \mathbb{N},\;A(i)
(más…)