Skip to content
Vamsi's Digital Garden

Fibonacci Numbers

This content is not available in your language yet.

:::note Binet’s formula

From the generating function, we have

∑n=0∞Fnxn=x1−x−x2=x+x2(1+x)+x3(1+x)2+⋯+xk+1(1+x)k+…\sum\limits_{n=0}^\infty F_nx^n = \frac{x}{1-x-x^2} = x + x^2(1+x) + x^3(1+x)^2 + \dots + x^{k+1}(1+x)^k + \dots

on comparing coefficients of xnx^n on both sides,

Fn=∑k=0⌊n−12⌋(n−k−1k)F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}

:::

:::note Property

From the generating function, we have

∑n=0∞Fnxn=x1−x−x2=x+x2(1+x)+x3(1+x)2+⋯+xk+1(1+x)k+…\sum\limits_{n=0}^\infty F_nx^n = \frac{x}{1-x-x^2} = x + x^2(1+x) + x^3(1+x)^2 + \dots + x^{k+1}(1+x)^k + \dots

on comparing coefficients of xnx^n on both sides,

Fn=∑k=0⌊n−12⌋(n−k−1k)F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}

:::