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:
a(1)=a(2)=1, a(n)=a(n-1)+a(n-2)
It is of course possible to find any term in the progression by simple calculations, but buy using this relation we are required to calculate all the terms which come before the one we want to know. It turn out that for high values of n this task is not practical even for a computer.
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:
c(n)=a(n)+b(n)=[a(n-1)+a(n-2)]+[b(n-1)+b(n-2)]
c(n)=a(n-1)+b(n-1)+a(n-2)+b(n-2)=c(n-1)+c(n-2)
q^(n-1)=q^(n-2)+q^(n-3)
q^2=q+1
q^2-q-1=0
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:
a(n)=a(n-1)+a(n-2)
g(n)=ra(n)=ra(n-1)+ra(n-2)=g(n-1)+g(n-2)
Thus, g(n) is also a generalized Fibonacci progression, and we proved that the group is closed to multiplication.
g(n)=ra(n)=ra(n-1)+ra(n-2)=g(n-1)+g(n-2)
Thus, g(n) is also a generalized Fibonacci progression, and we proved that the group is closed to multiplication.
c(n)=a(n)+b(n)=[a(n-1)+a(n-2)]+[b(n-1)+b(n-2)]
c(n)=a(n-1)+b(n-1)+a(n-2)+b(n-2)=c(n-1)+c(n-2)
The only thing we need to prove is that the dimension is two. To do this it is enough to show that there is a basis for this subspace that has two vectors in it. This is simple, the basis is the two progressions a(n)=1,0,... , b(n)=0,1,....
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:
aq^(n-1)=aq^(n-2)+aq^(n-3)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:
a(n)=aq^(n-1), a(n)=a(n-1)+a(n-2)
q^(n-1)=q^(n-2)+q^(n-3)
q^2=q+1
q^2-q-1=0
There is obviously a solution to this equation. Moreover, there are obviuosly two different solutions, and therefore two different progressions. Lets suppose that q(1) and q(2) are the solutions. We can also select a=1 because it doesn't influence the solution. We get then two progressions: a(n) and b(n). The only important thing left to do is to show that they are a basis to our vector space. Because I already prooved that the dimension is two, we just need to show that they are lineary independant. It ois enough to show that the solution of the following equations is a=b=0:
Since q(1) is not equal to q(2) this is indeed so and therefore we have a basis.
a+b=0, aq(1)+bq(2)=0
Since q(1) is not equal to q(2) this is indeed so and therefore we have a basis.
Now we know that any progression in our space can be written as c(n)=da(n)+fb(n) for some d,f. We also know that a(n)=q(1)^(n-1), b(n)=q(2)^(n-1). Deriving the final formula from this is easy, but since I still cannot use latex in blogger, completing the last step is left to the reader.
No comments:
Post a Comment