Non-Recursive FormulaDate: 06/05/2001 at 10:38:01 From: Dang Nguyen Duc Subject: General Fibonacci Sequence I want to know the non-recursive formula of the nth number in the general Fibonacci sequence. The general Fibonacci sequence is: F(n+k) = a1*F(n+k-1)+a2*F(n+k-2)+...+ak*F(n) I know that we can get it by solving this equation: x^k-a1*x^(k-1)-...-ak = 0 Could you explain why we come to this conclusion? Thanks. Dang Nguyen Duc Date: 06/05/2001 at 17:11:54 From: Doctor Rob Subject: Re: General Fibonacci Sequence Thanks for writing to Ask Dr. Math. If k = 1, you would have F(n+1) = a1*F(n). The solution to this is ("obviously") F(n) = c1*a1^n, for any constant c1. Also a1 is a root of the polynomial equation x - a1 = 0. Now suppose that F(n) = c1*r^n + c2*s^n, where alpha and beta are not equal. What equation would this satisfy? F(n+2) = c1*r^(n+2) + c2*s^(n+2), = c1*r^(n+1)*r + c2*s^(n+1)*s, = c1*r^(n+1)*(r+s) + c1*(-r*s)*r^n + c2*s^(n+1)*(r+s) + c2*(-r*s)*s^n, = (r+s)*F(n+1) + (-r*s)*F(n+2). Thus if we set r + s = a1, -r*s = a2, then F(n) will satisfy the recursion F(n+2) = a1*F(n+1) + a2*F(n). Now r and s are the roots of the equation (x-r)*(x-s) = 0, x^2 - (r+s)*x - (-r*s) = 0, x^2 - a1*x - a2 = 0. Thus the solution of the recursion F(n+2) = a1*F(n+1) + a2*F(n) is given by F(n) = c1*r^n + c2*s^n, for any constants c1 and c2, where r and s are distinct roots of the polynomial equation x^2 - a1*x - a2 = 0. The constants c1 and c2 are determined by the initial conditions on F(n). The same situation holds for a linear combination of k > 2 unequal exponential functions, except the degree of the equation is k. The coefficients of the equation are just the ones appearing in the recursion. (One has to make an adjustment to handle the case when the polynomial equation has repeated roots.) Another way to see this is to express the recursion in terms of the shift operator S which operates on sequences: S(F[n]) = F(n+1). Then the recursion can be rewritten in the form S^k(F[n]) - a1*S^(k-1)(F[n]) - ... - ak*F(n) = 0, or (S^k - a1*S^[k-1] - ... - ak)(F[n]) = 0. This says that the sequence F(n) is annihilated by the operator in parentheses. Now if this polynomial in S has distinct roots r1, r2, ..., rk, then (because S commutes with multiplication by constants) it can be factored into ([S-r1]*[S-r2]*...*[S-rk])(F[n]) = 0. Now the operator S - rk annihilates the sequence rk^n, and multiplies ri^n by a nonzero constant ri - rk. This means that applying these operators S - ri for i = k, k-1, ..., 2, 1 annihilates any linear combination of these exponential functions. (Again, if the polynomial has repeated roots, there is an adjustment which needs to be made.) Thus a set of solutions of this equation is F(n) = c1*r1^n + c2*r2^n + ... + ck*rk^n, for any constants c1, ..., ck. These constants are determined by the initial conditions on F(n). That this is all the solutions can be seen by the fact that the dimension k of the space of solutions is equal to the dimension k of this set of solutions, so this set is all there is. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/