Sequences

Let us define a sequence of numbers {f_m} by f₀ = 0, f₁ = 1 and
f_m+2 = f_m+1 + f_m , m≥0.
Its quite obvious that f_m is the the m-th Fibonacci number for m≥1.
Consider the power series
A(x) = f₀ + f₁ x + f₂ x² + . . . + f_m x^m + . . .
Its quite obvious that
A(x) - x A(x) - x² A(x) = f₀ + (f₁ - f₀) x = x
Hence, we get
A(x) = x1-x-x²
This, therefore, is the generating function for the sequence {f_m}.
Hence,
f_m+1 = coefficient of x^m+1 in the expansion of A(x)
= coefficient of x^m in the expansion of 11-x-x²
On the other hand, we have
\dfrac{1}{1-x-x^2} = \dfrac{1}{1-x(1+x)} = \sum_{n\ge 0}(x(1+x))^n
(that's just the GP formula)
That's further
\sum_{n\ge 0} x^n (1+x)^n =\sum_{n\ge 0}x^n \sum_{k\ge 0}~^nC_k x^k = \sum_{n\ge 0}\sum_{k\ge 0}~^nC_k x^{n+k}
In these notations
^nC_k = 0 if k > n.
Hence,
f_{m+1} = \sum_{\substack{n\ge k\ge0\\n+k=m}}~^nC_k

I want to share an Induction method to do the same:

First Step of induction is left.

Inductive Step:

\Sigma C(n+1,k) = \Sigma (C(n , k)) + \Sigma C(n , k-1) ;

since , C(n+1,k) = C(n , k) + C(n , k-1) ;

Which is equal to fm + fm-1;
so fm+1 = fm + fm-1 .

-------------------------------------------------
Please confirm it from teachers before using it, I am not completely sure about, just came in mind. Seemed Good , So Shared.

Which leads to Binets Formula ;)

Thank you