The Fibonacci sequence has provided endless hours of enjoyment
for mathematicians - both amateur and professional alike. For those of you
who are not familiar with this sequence, it is defined by the following
relation:
F(n+2) = F(n+1) + F(n) where F(1) = F(2) = 1
The first 21 terms of this sequence are:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, ...
A related sequence is called the Lucas sequence which is defined by:
L(n+2) = L(n+1) + L(n) where L(1)=1 and L(2) = 3
The first 21 terms of this sequence are:
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571,
5778,9349, 15127, 24476, ...
From these simple relations come endless mathematical patterns. I have listed several relations below. These relations are all known, and can be proven using the defined relations above. I have omitted other relations that involve the golden ratio, and focus only on those that use integers. References for these relations are listed at the end of this page.
F(2n) = F(n) * L(n)
L(n) = F(n+1) + F(n-1)
F(n)*5 = L(n+1) + L(n-1)
L(n)2 = 5F(n)2 + 4(-1)n
F(n+1)*F(n-1) - F(n)2 = (-1)n
L(n+1)*L(n-1) - L(n)2 = 5*(-1)n+1
Odd : F(2n+1) = F(n+1)2 + F(n)2
Even : F(2n) = F(n+1)2 - F(n-1)2
F(n+p+1) = F(n)*F(p) + F(n+1)*F(p+1)
F(3n+3) = F(n+1)3 + F(n+2) F(n)*F(p) - F(n-k)*F(p+k) = (-1)(n-k)*F(k)*F(p+k-n)
F(n+4)3 = 3F(n+3)3 + 6F)n+2)3 - 3
F(n+1)3 - F(n)3
sum[F(k)] = F(n+2) - 1 (k=1 to n)
sum[L(k)] = L(n+2) - 3 (k=1 to n)
sum[F(k)2] = F(n)*F(n+1) (k=1 to n)
sum[F(k)3] = [F(3n+2) + (-1)n+1*6*F(n-1) +5]/10
(k=1 to n)
sum[k*F(k)] = (n+1)*F(n+2) - F(n+4) + 2 (k=1 to n)
sum[F(k)*F(k+1)] = [F(2n-1) + F(n)*F(n-1) - 1]/2 (k=1 to n-1)
Even : sum[F(2k)] = F(2n+1) - 1 (k=1 to n) sum[C(n,k)*F(n-k)] = F(2n) (k=0 to n)
F(mn+p) = sum[C(m,k)*F(k+p)*F(n)k*F(n-1)m-k
(k=0 to m)
These are the known ones that I have accumulated over the years, and there
are undoubtedly many others. There is also a relationship of the Fibonacci numbers to the binomial
coefficients. If you sum the diagonals in the Pascal triangle shown below,
the sums equal the Fibonacci numbers. It takes a bit of patience to see
the diagonals in the triangle. The diagonals start with 1 on the left of the
triangle, and extend to the upper right.
Another fascinating aspect is that F(p) can be prime only if p is prime
or equal to 4.
But not all F(p) are prime. Therefore we see that F(3) = 2, F(4) = 3,
F(5) = 5, F(7) = 13, F(11) = 89, F(13) = 233, and F(17) = 1597 - all primes.
However p=19 is also prime, but F(19) = 4181 = 37*113 and is not prime.
I have been able to identify F(p) as
prime for p = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431,
433, 449, 509, 569, 571, 2971. In addition, Neil Sloane identifies prime
F(p) for p = 4723, 5387 and 9311. The value 9311 was discovered as recently
as 1995, and F(9311) is a very large number.
The way that Fibonacci relations are intertwined and nested within other
relations, never ceases to amaze me.
References
A Primer for the Fibonacci Numbers. The Fibonacci Association, The Art of Computer Programming. Vol.1. Fundamental Algorithms. Enjoy.
The next relations involve sums of the terms.
Odd : sum[F(2k+1)] = F(2n+2) - 1 (k=1 to n)
There are also associations with the binomial coefficients where:
C(n,k) = n!/((n-k)!k!)
Fibonacci numbers from Pascal's triangle
Diagonal sums Pascal's Triangle
1 1
1 1 1
1 + 1 = 2 1 2 1
1 + 2 = 3 1 3 3 1
1 + 3 + 1 = 5 1 4 6 4 1
1 + 4 + 3 = 8 1 5 10 10 5 1
1 + 5 + 6 + 1 = 13 1 6 15 20 15 6 1
1 + 6 + 10 + 4 = 21 1 7 21 35 35 21 7 1
1 + 7 + 15 + 10 + 1 = 34 1 8 28 56 70 56 28 8 1
and so on ...
Prime Fibonacci numbers
1973. Edited by M. Bicknell and V.E. Hoggatt, Jr.
San Jose State University, San Jose, California.
1973. D.E. Knuth. Addison-Wesley Pub.Co.
Last Modified July 8, 2003