Fibonacci Numbers

Binet's formula

From the generating function, we have

$$\sum _{n=0}^{\infty }{F}_n{x}^n=\frac{x}{1-x-x^2}=x+x^2(1+x)+x^3(1+x{)}^2+\cdots +x^{k+1}(1+x{)}^k+\dots$$

on comparing coefficients of $x^n$ on both sides,

$$F_n=\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }\left(\genfrac{}{}{0ex}{}{n-k-1}{k}\right)$$

Property

From the generating function, we have

$$\sum _{n=0}^{\infty }{F}_n{x}^n=\frac{x}{1-x-x^2}=x+x^2(1+x)+x^3(1+x{)}^2+\cdots +x^{k+1}(1+x{)}^k+\dots$$

on comparing coefficients of $x^n$ on both sides,

$$F_n=\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }\left(\genfrac{}{}{0ex}{}{n-k-1}{k}\right)$$