japhy
Enthusiast
Dec 15, 2000, 1:43 PM
Post #1 of 3
(50426 views)

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[n1] + F[n2]. And we could probably generate these numbers easily in Perl:
{ 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[$m1], $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 51. Notice that 1+1+2+3 is 7, which is 81. And 1+1+2+3+5 is 12, which is 131. So what do 5, 8, and 13 have in common? They're also three numbers in the sequence. 1+1+2 is 51, and 5 is the 2nd number after 2. 1+1+2+3 is 81, and 8 is the 2nd number after 3. 1+1+2+3+5 is 131, 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
