Relación entre el Pascal ' serie s triángulo y fibonacci.

Question

Accidentalmente, yo había visto a esta relación. Traté de encontrar la fórmula

Aquí está mi probar:-

$$f_0= {{0}\choose{0}} $$

$$f_1={{1}\choose{0}} $$

$$f_2={{2}\choose{0}}+ {{1}\choose{1}} $$

$$f_3= {{3}\choose{0}}+ {{2}\choose{1}} $$

$$f_4= {{4}\choose{0}}+ {{3}\choose{1}}+{{2}\choose{2}} $$ $$...$$

Generalizando,

$$f_n=\sum_{s+r=n,s\ge r}{{s}\choose{r}}, 0\le s,r \le n $$

Cómo escribir la fórmula correcta de n-ésimo término. ¿Por qué este patrón está por venir. Pude comprobar mediante el cálculo de hasta n=10. Cómo dar una rigurosa prueba?.

Answer 1

Deje $f_n$ el número de maneras de subir una escalera de $n$ de los niveles, cada vez que se puede cruzar a través de uno o dos pasos.

Hay dos maneras de evaluar esto. La primera forma es a través de la recursividad. Si el primer movimiento cruzaba por un paso, usted tiene $f_{n-1}$ formas de los cielos el resto; y si su primer movimiento cruzado a través de dos pasos, usted tiene $f_{n-2}$ maneras de hacer el resto. Por lo $f_n = f_{n-1} + f_{n-2}$. La condición inicial da $f_1 = 1$$f_2 = 2$, y usted puede ver que esto es de Fibonacci.

Por otro lado, usted puede encontrar una manera de describir a través de la combinatoria. Si subes a la totalidad de las escaleras de $n$ niveles en $n$ se mueve, luego cruzó un paso a $n$ veces y cruzó dos pasos de 0, así que hay $\binom {n}{0}$ formas de hacerlo. Si Si subes a la totalidad de las escaleras de $n$ niveles en $n-1$ se mueve, luego cruzó un paso a $n-1$ veces y cruzó dos pasos 1, así que hay $\binom {n-1}{1}$ formas de hacerlo. Y así sucesivamente ves que

$$ f_n = \binom {n}{0} + \binom {n-1}{1} + \binom {n-2}{2} + \cdots. $$