Unlike the previous posts on this subject, in this post instead of talking about the subject in general I will just fully solve one rather nontrivial problem. The problem is to find the formula for the n-th term of the Fibonacci progression.
The Fibonacci progression is a progression defined by the following relation:
To find the formula we will need to use linear algebra. Firstly, lets define a group of progressions which we will call generalized Fibonacci progressions. Those are all the progressions that follow the recursive rule, but the first terms are allowed to be any numbers. Now, lets look on the vector space of all infinite progressions. Obviously, the generalized Fibonacci progressions belong to this space. Moreover they form a subspace of dimension two in the vector space.
The last sentence requires a proof - all we need to show is that the group of the generalized Fibonacci progressions is closed under multiplication and addition. We will take two such series, a(n) and b(n) and a scalar r:
Thus, g(n) is also a generalized Fibonacci progression, and we proved that the group is closed to multiplication.
To prove that this is a basis we need to show that the vectors are independent (left as an exercise) and to show that any other vector is a linear combination of these two. Let c(n) be a vector in this space. All the generalized Fibonacci progressions are uniquely defined be their two first terms, so lets suppose that the two first terms are c(1)=d and c(2)=r. Then, f(n)=da(n)+rb(n)=d,r,....
Since we are in a vector space the resutl is another progression, and because of the unique definiton by the first two terms, we get that c(n)=f(n).
Now, is there a genarilized Fibonacci progression which is also a geometrical progression? We get the following conditions:
Since q(1) is not equal to q(2) this is indeed so and therefore we have a basis.