I have discovered an equation that generates powers of phi, the golden ratio ((5^.5+1)/2), but it relies on Fibonacci numbers for its output:
If x>=1, phi^x=F(x)phi+F(x-1)
If x<=-1, phi^x=(-1)^xF(x)*phi+(-1)^(x+1)*F(x-1)
phi^0=1
where F(x)=Fibonacci number x.
Since this equation calculates powers of phi, I can’t use an equation for Fib. numbers that uses powers of phi. Can anyone help me out here? (Do not inform me that F(x)=F(x-1)+F(x-2). I know that.)
Thanks for your help!
Rather than tell you the answer, let me show you how to solve this problem. We know f(x+2)=f(x+1)+f(x), and also that f(0)=f(1)=1.
This is a linear equation with constant coefficients so we guess a solution f(x) = Aa^x. Substituting this into the equation gives
Aa^(x+2) = Aa^(x+1) + Aa^x or a^2 = a + 1 or a^2 - a - 1 = 0
The last is a quadractic equation in a = [1 {+ or -} sqrt(5)]/2. That is a is equal to the golden ratio phi = 1.618034… or 1 - phi = -0…618034. So now we have the general solution as a linear combination of these two solutions for any constant A (called A and B for the two solutions)
f(x) = A*phi^x + B*(1-phi)^x
A and B can be determined by the two values we know.
1 = f(0) = A + B
1 = f(1) = A*phi + B*(1-phi).
Solving these two equations gives A = phi/(2phi - 1) B = (phi - 1)/(2phi - 1). So our final answer is
f(x) = [phi^(x+1) - (1-phi)^(x+1)]/(2*phi -1)
Yes, thank you, Oldguy, but since my equation is designed to compute phi^x, I can’t use an equation for Fibonacci numbers that needs phi^x. (Which, oddly enough, I think I mentioned in my OP.)
Dang it, why do I sound so cold and mean online? I really don’t mean to do that.
I hate to tell you, but the easy way to generate F[sub]n[/sub] is basically an inversion of your “discovered” equation. Want a closed form for F[sub]n[/sub]? It uses powers of phi.
Try Binet’s Formula, where x is the xth Fibonnaci number.
I think you mean F(x) is the xth Fibonacci number. Note that the (1+sqrt5)/2 in the formula is phi.
Maybe I should have phrased that better. x is the xth place of the Fibonacci sequence. f(x) is, indeed, the xth value in the Fibonacci sequence.
I must be slipping in my old age. I think I’ll just take Mathochist at his/her word.
The easiest way to calculate Fibonacci numbers by hand is through a method known as dynamic programming. Without getting into all the details, you keep a three place array with the first three Fibonacci numbers, and then calculate the next one by adding the previous two, mod 3. Does that make sense?
I’m curious. Was it or was it not decided that there is (or is not) a simple, closed form method?
I’ve thought that you have to use a subroutine, start from the beginning and go up to n each time you need to compute one of them…
It is far faster to compute Fibonacci numbers using repeated squaring. Either thru Binet’s formula or methods such as repeated squaring of the Fibonacci Q-Matrix. Ergo only a logarithmic number of operations are required rather than linear.
Yes, but that’s very quick, and easy to program.
There is a simple closed-form method for calculationg the Fibonacci sequence, but it uses powers of phi (which the OP wants to use Fibonacci to calculate). In fact, I already mentioned this in my response to the OP. Did I accidentally use the “invisible” tag?
This is an exposition of a simple closed-form method?
“I hate to tell you, but the easy way to generate Fn is basically an inversion of your “discovered” equation. Want a closed form for Fn? It uses powers of phi.”
“Did I accidentally use the “invisible” tag?”
Might as well have.
OK, I’ve been on a laptop all of last week, so my ability to post has been limited. Let’s briefly discuss various methods of calculating Fibonacci numbers.
As Mathochist alluded to, there is a closed form formula for calculating F[sub]n[/sub], but it relies on knowing the value of [symbol]f[/symbol], so that won’t do you any good. Since [symbol]f[/symbol] is an irrational number, you also may have to worry about floating point accuracy (but not unless you’re dealing with large values of n).
ftg’s methods are undoubtedly the fastest you’ll find easily, but I don’t think you’d consider them to be simple, especially if you’re doing this by hand. If you’re programming, it really depends on what environment you’re programming in–in C++, that’s the way to go, but on a TI-83, it’s not.
The dynamic programming method I outlined above is simple enough to be executed by hand and reasonably fast for small to medium values of n.
The traditional recursive method is actually one of the worst published algorithms I’ve seen. It fails because you end up computing each F[sub]k[/sub] (k < n) multiple times, and that gets expensive.
Of course, let’s not forget a very important fact here–the Fibonacci numbers don’t change between runs of your program. Stick them in a file, and do a lookup to see if you already know the value. If you do, return that; if not, compute that value and all the intermediate ones you don’t have, and stick those in the file.
Ah, but you asked if there exists such, not what it is.
F[sub]n[/sub] = (phi[sup]n[/sup] - (-phi)[sup]-n[/sup]) / sqrt(5)
