Conference rusure::math

    There is an international Fibonacci Bulletin devoted to this topic.
    Stan used to make contributions to it. I don't know of any extant
    copies, though.

    Fibonacci(n) is a built-in function in MAPLE. It will compute f(n)
    usually in less time than it takes to write it on the screen. N can be
    arbitrarily large. It requires that you type "readlib(fibonacci);"
    before using it.

		Proof by Induction of Problem 3 of 545.0

Build a pyramid of binomial coefficients:

		  1                         0
                                            0
	        1   1    	      	  1   1
                                          0   1
	      1   2   1         =       2   2   2
	                                0   1   2
	    1   3   3   1             3   3   3   3
	                              0   1   2   3
	  1   4   6   4   1         4   4   4   4   4
	                            0   1   2   3   4
	1   5  10  10   5   1     5   5   5   5   5   5
	                          0   1   2   3   4   5
and annotate it:
         			    A0
			          B0  C1
			        C0  D1  E2
		              D0  E1  F2  G3
		            E0  F1  G2  H3  I4
                          F0  G1  H2  I3  J4  K5

Then Problem 3 of 545.0 can be restated as:

	U(1) = sum of Aj = 1
	U(2) = sum of Bj = 1
	U(3) = sum of Cj = 1 + 1 = 2
	U(4) = sum of Dj = 1 + 2 = 3
	U(5) = sum of Ej = 1 + 3 + 1 = 5
	U(6) = sum of Fj = 1 + 4 + 3 = 9
	etc.

All over the pyramid, each number is the sum of the two numbers diagonally
above it:
		(letter, j) = (previous_previous_letter, j - 1)
			      + (previous_letter, j)

So:
	sum of (letter, j) = sum of (previous_previous_letter, j - 1)
			     + sum of (previous_letter, j)

(for example:  sum of Fj = sum of Dj + sum of Ej

	 	       		    ..
			          ..  ..
			        ..  D1  E2
		              D0  E1  F2  ..
		            E0  F1  ..  ..  ..  
                          F0  ..  ..  ..  ..  ..  )

[Each sum goes from j = 0 to j = floor ( (appropriate_letter - A) / 2), which
 turns out to be what was asked for.]

Then, by induction, the sums of Gj, Hj, Ij, ... continue to track the
Fibonacci numbers.

John

Let see if we can solve the first problem in .0

Recall:

    >   [1]  Show that the sum of the first  n  Fibonacci numbers with odd
    >        indices is given by the formula:
    >
    >         U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)
    >
    >        and that the sum of the first  n  Fibonacci numbers of even 
    >        indices is given by the formula:
    >
    >         U(2) + U(4) + U(6) + ... + U(2n) = U(2n+1) - 1


    well the Fibonacci sequence is

        { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... }

    and 

        U(1) = U(2) = 1

        U(3) = U(4) - U(2) = 2

        U(5) = U(6) - U(4) = 3
                  .
                  .
                  .
        U(n) = U(n+1) - U(n-1)


    so to show that 

        U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)
 
    substitute  
                U(2)            for   U(1)   
                U(4)-U(5)       for   U(3)
                U(6)-U(4)       for   U(5)
                ... etc

    we get

       U(2) + (U(4)-U(2)) + (U(6)-U(4)) + ... + (U(2n)+U(2n-2)) = U(2n)

       and U(2) cancels with -U(2), ... etc.
 
    so 

       U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)


    I will let someone else show the second half of [1]
    i.e. 

    >  [1]b  
    >        and that the sum of the first  n  Fibonacci numbers of even 
    >        indices is given by the formula:
    >
    >         U(2) + U(4) + U(6) + ... + U(2n) = U(2n+1) - 1



    Enjoy,

    Kostas G.

    There hasn't been a whole lot of talk about Fibonacci numbers for
    a while, so I'll toss out this result that I literally stumbled
    upon (looking for something else) some time ago.  I don't know if
    this is common knowledge among Fibonaccians, but I've never seen
    it anywhere.  My apologies for using a slightly different
    representation of the sequence; starting at zero made things easier
    for me with respect to the other problem I was working.  By the
    way, the other problem had to do with musical applications - how
    many rhythmic patterns are there of a given length obeying a certain
    contraint.  I have also discovered the sequence plays a quite prominent
    role in the analysis of paradiddles, i.e., strings on the alphabet
    {1, 2} with the constraint that the same character may occur no
    more than twice in succession.
    
    If any of this seems naive, please bear with me, I am not a
    mathematician and have only been trained in traditional engineering
    mathematics.  I do, however, enjoy fooling around with mathematics.
     
    Let F(x) be the x'th Fibonacci number [F(x) = U(x+1) using the notation
    prevalent in this note]:
   
     F(0) = 0
   
     F(1) = 1
   
     F(i) = F(i-1) + F(i-2) for i > 1
   
    Note that you can define F(i) for i < 0 as F(i-1) = F(i+1) - F(i);
    the result is
   
     F(-i) = (-1)^(i-1) * F(i)


    Then
   
     F(x+y) = F(x-1)*F(y) + F(x)*F(y+1)

    Note that since x+y = y+x, this means that it's also true that

     F(x+y) = F(y-1)*F(x) + F(y)*F(x+1)

    The two possible forms are thus:
   
     F(x+y) = F(x-1)*F(y) + F(x)*F(y+1)
   
     F(x+y) = F(x+1)*F(y) + F(x)*F(y-1)
   
    It is straightforward to demonstrate that these two expressions are equal.

      
    Proof by induction:
   
     F(x+i) = F(x-1)*F(i) + F(x)*F(i+1)

    This is easily demonstrated to be true for i = 0 and 1:
   
     F(x+0) = F(x-1)*F(0) + F(x)*F(1) = F(x)
   
     F(x+1) = F(x-1)*F(1) + F(x)*F(2) = F(x-1) + F(x),
   
    since F(1) = 1 and F(2) = 1.
 
    Now demonstrate that it's also true for i+1.  This is easily done:

     F(x+(i+1)) = F((x+i)+1) = F((x+i)-1)*F(1) + F(x+i)*F(2)

    As noted above, F(1) = 1, F(2) = 1, so

     F(x+(i+1)) = F((x+i)+1) = F((x+i)-1) + F(x+i),
   
    which is true by definition (i.e., F(n+1) = F(n) + F(n-1).)
   

   
    len.
    

    I posted the previous reply about 6 months ago and there hasn't
    been any reaction.  Is this an obvious result known to all?
    How would I find out if this is old hat or something new?
    
    len.
    

See Knuth, "The Art of Computer Programming", Vol. I, P. 80, formula (6).

(By the way, there is a misprint in the formula, in the 1st edition. 
'm+1' should be 'm-1'.) 

Lynn Yarbrough 

    Aha, thanks!  Should have just looked it up (wouldn't have expected
    to find it in Knuth though) rather than burn out all those neurons
    deriving it...
    
    len.
    

Article: 22027
From: clong@remus.rutgers.edu (Chris Long)
Newsgroups: rec.puzzles,sci.math
Subject: Molly's Rabbit Farm
Message-ID: <Oct.26.03.03.47.1991.9621@remus.rutgers.edu>
Date: 26 Oct 91 07:03:47 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
 
 
Molly, Waldo's niece, wants to become a millionaire.  Not an
easy thing to do, but she has a plan - she's going to raise and
sell rabbits.  Not just any rabbits, but Fibonacci rabbits.  These
are very special rabbits!  They are immortal, they mature in only
one day, and mature Fibonacci rabbits produce (asexually) exactly
one offspring per day.
 
Assuming she has a buyer who will pay her $1 per rabbit, but only once,
what is the minimum number of rabbits she would need to have initially
in order to make a million dollars exactly?
-- 
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ  08901  (908) 846-5569
 
"The proofs are so obvious that they can be left to the reader."
Lars V. Ahlfors, _Complex Analysis_

>...			They are immortal, they mature in only
>one day, and mature Fibonacci rabbits produce (asexually) exactly
>one offspring per day.

If I interpret this correctly, if we start with 1 rabbit we will have 1, 2,
4, 8, ... 2^n rabbits after n days. To avoid fractional rabbits, we can
only deal with as many reproductions are there are powers of 2 in
1,000,000: 6. So we have to start with 5^6 = 15625 to get there. The total
for each day is 15625, 31250, 62500, 125000, 250000, 500000, 1000000. 

    .12 is clearly wrong. The author misses the point of a Fibonacci rabbit
    taking one day to mature. The sums go like this -
    
    Day  Baby rabbits  Mature rabbits  Total
    ---  ------------  --------------  -----
    
    1         1               0          1
    2         0               1          1
    3         1               1          2
    4         1               2          3
    5         2               3          5
    6         3               5          8
    
    etc. Hence the name "Fibonacci" rabbit.
    
    Brian

>...			They are immortal, they mature in only
>one day, and mature Fibonacci rabbits produce (asexually) exactly
>one offspring per day.

It's not all that clear. If we start with 1 rabbit, it has another on the 
first day. On the second day *both* are mature and have another pair. On 
the 3rd day all 4 are mature and have 8 ...

Anyhow, let's assume that the growth rate is indeed Fibonaccian. The ratio 
of terms in a F-series is (1+5^.5)/2, so on day n-1 we would have 1000000
* .6180339 = 618034 and on day n-2, 381966, ... Continuing to work 
backwards, we arrive at 144 and 298 as the lowest positive increasing
numbers in the sequence. So we must start with 154 immature bunnies and 144
mature ones that reproduce on the first day, and everybody contributing as 
they mature on later days. The complete sequence is 

(154, 144)= 298, 442, 740, 1182, 1922, 3104, 5026, 8130, 13156, 21286, 34442,
55728, 90170, 145898, 236068, 381966, 618034, 1000000.

    
    Silly me...I interpreted the question in yet a third way viz. that our
    rabbit raiser starts off with only young ones. Whereas the answer to
    the question is then very easy, it leads to some interesting side
    problems if one considers generalising 1000000 to some other target. (BTW
    I haven't actually solved any of these other problems.)
    
re .14
    
>The ratio of terms in a F-series is (1+5^.5)/2
    
    This is the asymptotic ratio of consecutive terms of the sequence.
    
    Can you give some justification for your procedure?

>    Can you give some justification for your procedure?

Hmm. Well, actually I did a bit of inspired guessing. I assumed 1000000 is 
large enough so that the actual ratio and the asymptotic ratio were close 
enough for gov't work, and thus that the previous head count was 1000000/
((1+5^.5)/2) ~= 618034. I worked backward from that figure to get the
results in .-2, then checked the possibilities 618033 and 618035, and found
that they indeed are worse (i.e. larger initial headcount). I then asssumed
that numbers still farther from 618034 would be still worse, and didn't
check them. 

The last three positive terms in the sequence, 298, 144, 154, are followed 
by -10. After considering how these numbers might be used to describe the 
initial state, I decided that 298 rabbits, 144 adults and 154 juveniles,
made sense but that no smaller combination did.

    re .the original question (yet another misinterpretation)
    
    I make the answer 5 (babies).
    
    The largest Fibonacci number not greater than our target population of
    1000000 is 832040. This latter amount can be generated from just one
    baby. Subtracting this leaves a remainder of 167960. Repeating the
    process a few more times gives 55 which is a Fibonacci number. Thus by
    the timely addition of single babies it can be shown that the rabbit
    raiser needs only 5 babies to make her million.
    
    (Yes, I realise the original question implied that the initial rabbits
     were purchased all at the same time.)

This is the list of a program for factorizing Fibonacci numbers. This program
executes on an alpha axp OSF/1 system.

To compile:

# cc fib.c -o fib
# fib 93

Note: f_93 is the largest Fibonacci which fits in our alpha chip 64 bits 
register.

I apologize for the poor comments: this is only a hobbyist program.
But when I write a program in a professional purpose, I usually try to 
self document it with as many comments as possible. 

There exist perfect numbers, but not perfect programmers...



#include	<stdio.h>
main (argc, argv)
int	argc;
char	*argv[];
{
unsigned long int	f0, f1, f2, i, n;	/* These are 64 bits alpha */
						/* axp integers            */

if(argc < 2) exit(0);		
n = atoi(argv[1]);	/* Tell how many numbers you want in command line */
f0 = 0;
f1 = 1;
printf("f0 = 0\nf1 = 1\n");
for(i = 2; i <= n; i++)
{
    printf("f%d = %lu", i, f2 = f1 + f0); 
    if(f2 >1)
	{
	    printf(" = ");
	    dfp(f2,i);		/* Call the factorization routine */
	}
    printf("\n");
f0 = f1;
f1 = f2;
}

}

dfp(n,x)		/* Factorise the number n, which is the x-th fibo*/
unsigned long int n,x;
{
unsigned long int	d,q,r,a;

if(testp(x))		/* checks whether the rank is prime */
   {
	d = 2 * x - 1;
	a = 2;
   }
else
   {
    d=2;
    a=0;
   }
while( n > 1)
{
q = n/d;
if(q < d)
   { 
	printf("%lu", n); 	/* found last divisor, and it is prime */
	return;
   }
r=n%d;
if(r==0)
    {
	printf("%lu ", d);	/* found a divisor */
	fflush(stdout);
	n = q ;
    }
else
   {
	if(a==0)		/* The rank is not prime, so we */
				/* clumsily try to divide the number by */
				/* all integers less than its sqrt */
    	    d++;
	else			/* The rank is prime, so we try to divide */
				/* the number only by the numbers in the */
				/* form k*x-1 or k*x+1 - see note .-1,theorem 5*/
            {
	      d += a;
	      a = 2*x - a;
	    }
   }

}

}

testp(x)			/* Checks whether x is an (odd) prime */
unsigned long int x;
{
int d;
if(x <= 2) return 0;		/* x is not odd */

for(d=2;;d++)
{
if(x/d < d) return 1;		/* x is prime */
if(x%d == 0) return 0;		/* x is not prime */
}
}


Here is the output of the program (took about 30 seconds of computing time 
on a DEC3000)

f0 = 0
f1 = 1
f2 = 1
f3 = 2 = 2
f4 = 3 = 3
f5 = 5 = 5
f6 = 8 = 2 2 2
f7 = 13 = 13
f8 = 21 = 3 7
f9 = 34 = 2 17
f10 = 55 = 5 11
f11 = 89 = 89
f12 = 144 = 2 2 2 2 3 3
f13 = 233 = 233
f14 = 377 = 13 29
f15 = 610 = 2 5 61
f16 = 987 = 3 7 47
f17 = 1597 = 1597
f18 = 2584 = 2 2 2 17 19
f19 = 4181 = 37 113
f20 = 6765 = 3 5 11 41
f21 = 10946 = 2 13 421
f22 = 17711 = 89 199
f23 = 28657 = 28657
f24 = 46368 = 2 2 2 2 2 3 3 7 23
f25 = 75025 = 5 5 3001
f26 = 121393 = 233 521
f27 = 196418 = 2 17 53 109
f28 = 317811 = 3 13 29 281
f29 = 514229 = 514229
f30 = 832040 = 2 2 2 5 11 31 61
f31 = 1346269 = 557 2417
f32 = 2178309 = 3 7 47 2207
f33 = 3524578 = 2 89 19801
f34 = 5702887 = 1597 3571
f35 = 9227465 = 5 13 141961
f36 = 14930352 = 2 2 2 2 3 3 3 17 19 107
f37 = 24157817 = 73 149 2221
f38 = 39088169 = 37 113 9349
f39 = 63245986 = 2 233 135721
f40 = 102334155 = 3 5 7 11 41 2161
f41 = 165580141 = 2789 59369
f42 = 267914296 = 2 2 2 13 29 211 421
f43 = 433494437 = 433494437
f44 = 701408733 = 3 43 89 199 307
f45 = 1134903170 = 2 5 17 61 109441
f46 = 1836311903 = 139 461 28657
f47 = 2971215073 = 2971215073
f48 = 4807526976 = 2 2 2 2 2 2 3 3 7 23 47 1103
f49 = 7778742049 = 13 97 6168709
f50 = 12586269025 = 5 5 11 101 151 3001
f51 = 20365011074 = 2 1597 6376021
f52 = 32951280099 = 3 233 521 90481
f53 = 53316291173 = 953 55945741
f54 = 86267571272 = 2 2 2 17 19 53 109 5779
f55 = 139583862445 = 5 89 661 474541
f56 = 225851433717 = 3 7 7 13 29 281 14503
f57 = 365435296162 = 2 37 113 797 54833
f58 = 591286729879 = 59 19489 514229
f59 = 956722026041 = 353 2710260697
f60 = 1548008755920 = 2 2 2 2 3 3 5 11 31 41 61 2521
f61 = 2504730781961 = 4513 555003497
f62 = 4052739537881 = 557 2417 3010349
f63 = 6557470319842 = 2 13 17 421 35239681
f64 = 10610209857723 = 3 7 47 1087 2207 4481
f65 = 17167680177565 = 5 233 14736206161
f66 = 27777890035288 = 2 2 2 89 199 9901 19801
f67 = 44945570212853 = 269 116849 1429913
f68 = 72723460248141 = 3 67 1597 3571 63443
f69 = 117669030460994 = 2 137 829 18077 28657
f70 = 190392490709135 = 5 11 13 29 71 911 141961
f71 = 308061521170129 = 6673 46165371073
f72 = 498454011879264 = 2 2 2 2 2 3 3 3 7 17 19 23 107 103681
f73 = 806515533049393 = 9375829 86020717
f74 = 1304969544928657 = 73 149 2221 54018521
f75 = 2111485077978050 = 2 5 5 61 3001 230686501
f76 = 3416454622906707 = 3 37 113 9349 29134601
f77 = 5527939700884757 = 13 89 988681 4832521
f78 = 8944394323791464 = 2 2 2 79 233 521 859 135721
f79 = 14472334024676221 = 157 92180471494753
f80 = 23416728348467685 = 3 5 7 11 41 47 1601 2161 3041
f81 = 37889062373143906 = 2 17 53 109 2269 4373 19441
f82 = 61305790721611591 = 2789 59369 370248451
f83 = 99194853094755497 = 99194853094755497
f84 = 160500643816367088 = 2 2 2 2 3 3 13 29 83 211 281 421 1427
f85 = 259695496911122585 = 5 1597 9521 3415914041
f86 = 420196140727489673 = 6709 144481 433494437
f87 = 679891637638612258 = 2 173 514229 3821263937
f88 = 1100087778366101931 = 3 7 43 89 199 263 307 881 967
f89 = 1779979416004714189 = 1069 1665088321800481
f90 = 2880067194370816120 = 2 2 2 5 11 17 19 31 61 181 541 109441
f91 = 4660046610375530309 = 13 13 233 741469 159607993
f92 = 7540113804746346429 = 3 139 461 4969 28657 275449
f93 = 12200160415121876738 = 2 557 2417 4531100550901

    

    re .19
    
    For those of us who still swear by VMS here's the same program editted
    to compile on Alpha VMS. (Took 40 CPU seconds on my DEC 4610.)
    
#include <stdio.h>
#include <stdlib.h>
#include <ints.h>

testp(x)			/* Checks whether x is an (odd) prime */
uint64 x;
{
int d;
if(x <= 2) return 0;		/* x is not odd */

for(d=2;;d++)
{
if(x/d < d) return 1;		/* x is prime */
if(x%d == 0) return 0;		/* x is not prime */
}
}

dfp(n,x)		/* Factorise the number n, which is the x-th fibo*/
uint64 n,x;
{
uint64	d,q,r,a;

if(testp(x))		/* checks whether the rank is prime */
   {
	d = 2 * x - 1;
	a = 2;
   }
else
   {
    d=2;
    a=0;
   }
while( n > 1)
{
q = n/d;
if(q < d)
   { 
	printf("%Lu", n); 	/* found last divisor, and it is prime */
	return;
   }
r=n%d;
if(r==0)
    {
	printf("%Lu ", d);	/* found a divisor */
	fflush(stdout);
	n = q ;
    }
else
   {
	if(a==0)		/* The rank is not prime, so we */
				/* clumsily try to divide the number by */
				/* all integers less than its sqrt */
    	    d++;
	else			/* The rank is prime, so we try to divide */
				/* the number only by the numbers in the */
				/* form k*x-1 or k*x+1 - see note .-1,theorem 5*/
            {
	      d += a;
	      a = 2*x - a;
	    }
   }

}

}


main (argc, argv)
int	argc;
char	*argv[];
{
uint64 f0, f1, f2, i, n;	/* These are 64 bits alpha */
						/* axp integers            */

if(argc < 2) exit(0);		
n = atoi(argv[1]);	/* Tell how many numbers you want in command line */
f0 = 0;
f1 = 1;
printf("f0 = 0\nf1 = 1\n");
for(i = 2; i <= n; i++)
{
    printf("f%d = %Lu", i, f2 = f1 + f0); 
    if(f2 >1)
	{
	    printf(" = ");
	    dfp(f2,i);		/* Call the factorization routine */
	}
    printf("\n");
f0 = f1;
f1 = f2;
}

}

        re .18
        
        The proofs of these are very similar to a proof of one
        direction of the Lucas-Lehmer test for primality of Mersenne
        numbers (see note 2.5).  There you extend F_p with sqrt(3) if
        q is an odd prime and p = 2^q - 1 is prime.
        
        Dan

        Just like the Fibonacci numbers come from a recurrence, you
        can also define the recurrence
        
        	A(0) = 2
        	A(1) = 4
        	A(n+2) = 4A(n+1) - A(n)			n = 0,1,2,...
        
        Solving this yields
        
        	A(n) = (2 + sqrt(3))^n + (2 - sqrt(3))^n
        
        and a minor manipulation shows that
        
        	A(2n) = (A(n))^2 - 2
        
        The Lucas-Lehmer test uses the sequence
        
        	LL(0) = 4
        	LL(n+1) = (L(n)^2 - 2)   (in real life, take this mod 2^q - 1)
        
        and can be seen to be really computing LL(n) = A(2^n).  For
        odd primes q, N = 2^q - 1 is prime iff L(q-2) = A(2^(q-2))
        = A((N+1)/4) is 0 modulo N.
        
        You can compute the n-th element of any linear recurrence in a
        number of "steps" proportional to log(n), just as the above
        computes A(2^k) by taking the steps A(1), A(2), A(4), A(8), ....
        But where n is not a power of 2 you have a lot more overhead
        than when n is a power of 2.  And computing residues modulo 2^q - 1
        is a lot easier on a binary machine than computing residues modulo
        an arbitrary number.  Both of these should combine to make the
        Lucas-Lehmer test for a k-bit Mersenne number faster than a
        similarly motivated test for a k-bit Fibonacci number.
        
        Dan