nemesis wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> For instance, the second problem looks iterative, but there is a direct
>> formula for any member of the Fibonacci series
>> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
> 
> hmm, did you find out the formula for yourself or looked it up somewhere?  Most
> of the fun in solving these puzzles is coming up with solutions by yourself...

	Not too hard if you've studied difference equations (they also go by
another name - forgot what it was).

	The Fibonacci sequence is a simple difference equation: Linear,
homogeneous and constant coefficients. If this sounds like what you may
have learned in differential equations, it's because they can be solved
in almost the same way. Basically, assume a solution of the form a^n,
plug it into the Fibonacci equation and calculate the possible values of
a. You'll get two, and any linear combination of those two will satisfy
the equation. Plug in the initial conditions, and you've solved it.

	To get the partial sum of a Fibonacci sequence, note that it is just
the difference of two geometric sums. A little alteration in indices
gives you the sum of just the even terms.

	Having said all this, I just wrote a program to calculate it. One of
the people on the forums had a neat solution: For large n, the ratio of
two successive Fibonacci numbers is phi, the Golden Ratio. So his code
just started with 2, multiplied by phi^3 (as we only want the even
numbers), and rounded to the nearest integer after each iteration.

-- 
Best file compressor around: DEL *.* (100% compression)


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message