I''m not sure either of these exist, but I''m looking for two mathematical equations, one that will yield a Fibinacci number given it''s index and another that will yield a Factorial . Now I don''t mean an iterative or recursive formula but rather a set equation. For a simple series it''s obvious that: 1+2+3+4+5+6+7+8+9+10 = 55 and 4+5+6+7+8 = 30 to achieve the results needed you could iterate through a for loop, but you could also use these equations: Pending... Count = (First - Last) + 1 Multiplier = (Count div 2) For an even count: X = (First + Last) * Multiplier For an odd count: X = (First + Last) * Multiplier + (Last - Multiplier) These equations return a valid summation for all positive consecutive series. I''m looking for something along the same lines but in regards to Fibinacci and Factorials. First off, do they exist? I''d hate to sit hours on end trying to derive an equation that just doesn''t exist. Secondly if one or the other does exist, where can I find information on their implementation. Feel free to post an answer/explanation to either if you have it. Thanks in advance.

Fibinacci is i!/(j!(i-j)!) where i is the row and j is the position within the row starting at 0. As for factorial it is the integral of t^(z-1)*e(-t) with respect to t evaluated from 0 to infinity where z is n+1 and n is the number you are finding the factorial for, i.e. gamma(n+1). As for how to efficently evaluate that I would have to refer you to Numerical Recipes in C.

Can you explain what you mean by i is the row? For example if I were looking for F(n) to return the n position Fibinacci number I assume n would be replaced with j , but then what is i ? I don''t understand where I get that number from.

Someone suggested Binet''s Formula to me:

F(n) = (((1 + 5 ^ ½) / 2) ^ n + ((1 - 5 ^ ½) / 2) ^ n) / 5 ^ ½

which roughly simplifies to:

F(n) = ((1.618033989 ^ n) + (-0.6180339887 ^ n)) / 2.2360679774

and requires no iteration. Of course it''s not 100% accurate and little rounding is necessary to return the proper integer values, but that''s easy enough to do. The only exception is when n=1 F(n)=.4472135954, and standard rounding would yeild 0, so in that case you just handle it. All the other approximations should fall into place though.

Heh, that factorial integral just crashed my TI-89

(Note, here I''m saying F_1=F_2=1 and F_{n+1}=F_n+F_{n-1} for n>=2)

Yeah there is Binet''s formula: a=(1+rt(5))/2, b=(1-rt(5))/2
F_n=(a^n-b^n)/rt(5)
(This /is/ exact up to rounding, but to the precision of your floating point type and doubles. If I''m not mistaken the previous post had this slightly wrong, which is why it didn''t work for n=1)

Also, since b is small,
F_n is round(a^n/rt(5)) (where round is to the nearest integer)

Now I''ll go and answer a question that wasn''t asked, just because

While you can use Binet''s formula for Fibonacci numbers, you''d then be stuck using exponentiation and doubles..eww. If you''re ever actually using this in a program, you may be better off just precalculating a table (or using a non-recursive loop). This is especially true since F_47 will already not fit in a signed 32 bit int.

If you want, you can also calculate the n_th Fibonacci using matrices (and you don''t have to mess with exponentiation of doubles)
Let
a= |1 1|
|1 0|

Then, F_n is the top-right element in a^n. (Confirm this for small n if you''re skeptical, it is easy to prove by induction with the defintion of matrix multiplication)

I guess you could call this a formula too...after all its only exponentiation

How is this faster than the O(n) simple-loop method?
Well, what''s the run time for calculating a^n? The simplest way to calculate a factorial is just to multiply the identity by a, multiply the result by a, and so on N times. This would be O(n) and in fact a slower O(n) than the loop. But that''s not optimal, exponents can be calculated faster (O(log n)) by just calculating a^(2^k) (by repeated squaring) and multiplying those powers which are in n''s binary representation into the result.