One beautiful (and mathematically simple) way of analyzing this system is by the use of linear algebra. The idea is that, because F(n+1) depends linearly on F(n) and F(n-1) (see the above definition), then we can write the previous system with the following (linear-algebraic) notation
If we write x(n+1) as the vector (F(n), F(n+1)), i.e., first entry is F(n) and the second entry is F(n+1), and the matrix as A, then x(n+1) = Ax(n). (Note that A is the matrix whose entries are exactly the coefficients of the linear equation we gave above!)
In other words, we've reduced the problem down to the question of investigating the properties of the matrix A ! Now, the sum we were looking at, originally, can be written (in terms of x(n)) as the first entry of (note that x is a vector as we've defined it!)
The nth and (n+1)st fibonacci numbers can be written as a system of two equations in the nth and (n-1)st numbers:
where the base cases are F(0) = 0 and F(1) = 1.The question is then to show that (note that the indices under F are actually wrong in the OP...):
One beautiful (and mathematically simple) way of analyzing this system is by the use of linear algebra. The idea is that, because F(n+1) depends linearly on F(n) and F(n-1) (see the above definition), then we can write the previous system with the following (linear-algebraic) notation If we write x(n+1) as the vector (F(n), F(n+1)), i.e., first entry is F(n) and the second entry is F(n+1), and the matrix as A, then x(n+1) = Ax(n). (Note that A is the matrix whose entries are exactly the coefficients of the linear equation we gave above!)In other words, we've reduced the problem down to the question of investigating the properties of the matrix A ! Now, the sum we were looking at, originally, can be written (in terms of x(n)) as the first entry of (note that x is a vector as we've defined it!)
There's a slick proof (see [0]) that, if this sequence converges, then its result is given by the first entry of which is exactly what the result gives. (I have changed the normalization a little bit for convenience, but it is the same proof :)-----
[0] If
But, here's the magic! Let's subtract the first equation from the second to get so, multiplying by the inverse of B on both sides, we get: as required!