CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr
 MAIN INDEX SEARCHPOSTS WHO'S ONLINE LOG IN

Home: Fun With Perl: Perl Quizzes - Learn Perl the Fun Way:
Fibonacci

japhy
Enthusiast

Dec 15, 2000, 1:43 PM

Post #1 of 3 (52142 views)
 Fibonacci Can't Post
Sure, we all know the fibonacci set (1, 1, 2, 3, 5, 8, 13, 21, ...), and we all know the general equations: F[1] = F[2] = 1, and F[n] = F[n-1] + F[n-2].

And we could probably generate these numbers easily in Perl:

 Code
`{   my @fib = (1,1);   # generate the Nth fibonacci number   sub fibonacci {     my \$n = shift() - 1;     unless (\$fib[\$n]) {       my \$m = \$n;       \$m-- while not \$fib[\$m];       \$fib[\$m+1] = \$fib[\$m] + \$fib[\$m-1], \$m++ while \$m <= \$n;     }     return \$fib[\$n];   } }`
There's your fibonacci code. So what is it this quiz is all about?

I am here to tax your mathematical prowess. Notice that 1+1+2 is 4, which 5-1. Notice that 1+1+2+3 is 7, which is 8-1. And 1+1+2+3+5 is 12, which is 13-1. So what do 5, 8, and 13 have in common? They're also three numbers in the sequence. 1+1+2 is 5-1, and 5 is the 2nd number after 2. 1+1+2+3 is 8-1, and 8 is the 2nd number after 3. 1+1+2+3+5 is 13-1, and 13 is the 2nd number after 5. Do you see the pattern?

So I'd like any able mathematicians out there to develop a proof, which states that F[1] + F[2] + ... + F[k] = F[k+2] - 1 for all k > 0.

(So maybe this isn't a Perl quiz, but this problem is directly related to a specific anomoly in Huffman encoding, which is a simple means of compressing files. It turns out that Huffman coding is very inefficient for files whose character frequencies are the Fibonacci sequence.)

(If that last paragraph made no sense, nevermind. Just try the proof. It's fun.)

Jeff "japhy" Pinyan -- accomplished hacker, teacher, lecturer, and author

jas
Deleted

Dec 19, 2000, 6:59 AM

Post #2 of 3 (52129 views)
 Re: Fibonacci [In reply to] Can't Post
A bit of induction action:

Suppose F[1]+F[2]+...+F[k] = F[k+2]-1 for some k>0. We can safely assume this since at least for k=1,1+1+2=4=5-1.

We want to show that F[1]+F[2]+...+F[k]+F[k+1] = F[k+3]-1 ie. that the formula still holds.
But, F[k+3]-1=F[k+2]+F[k+1]-1 from the definition of Fibonacci numbers.
So, F[1]+F[2]+...+F[k]+F[k+1]=F[k+3]-1
becomes F[1]+F[2]+...+F[k]+F[k+1]=F[k+1]+F[k+2]-1
which reduces to F[1]+F[2]+...+F[k]=F[k+2]-1 which by our assumption is true.

So since the truth of the statement for F[k] implies the truth of the statement for F[k+1] and the statement is true for F[1], by mathemagical induction, the statement must be true for all k>0.

japhy
Enthusiast

Dec 19, 2000, 7:18 AM

Post #3 of 3 (52128 views)
 Re: Fibonacci [In reply to] Can't Post
Nice first post, jas! Well done, too.

(Inside tip, re: your web site: coup d'&eacute;tat.)

Jeff "japhy" Pinyan -- accomplished hacker, teacher, lecturer, and author

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0