Fibonacci number: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Karsten Meyer
mNo edit summary
mNo edit summary
 
(37 intermediate revisions by 9 users not shown)
Line 1: Line 1:
<!-- Taken from en.wikipedia.org/wiki/Fibonacci number -->
{{subpages}}
In mathematics, the '''Fibonacci numbers''' form a [[sequence]] defined by the following [[recurrence relation]]:
 
In mathematics, the '''Fibonacci numbers''' form a [[sequence]] in which the first number is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers in the series. In mathematical terms, it is defined by the following [[recurrence relation]]:
:<math>  
:<math>  
   F_n :=   
   F_n :=   
Line 9: Line 10:
   \end{cases}
   \end{cases}
  </math>
  </math>
<!-- Taken from en.wikipedia.org/wiki/Fibonacci number -->


The sequence of fibonacci numbers start: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...


==Fibonacci numbers and the rabbits==
The sequence of Fibonacci numbers starts with : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... 
 
It was first used to represent the growth of a colony of rabbits, starting with a single pair of rabbits.  It has applications in mathematics as well as other sciences, and is a popular illustration of recursive programming in computer science.
 
==Divisibility properties==
 
We will apply the following simple observation to Fibonacci numbers:
 
if three integers <math>\ a,b,c,</math>&nbsp; satisfy equality <math>\ c = a+b,</math>&nbsp; then
 
::<math>\ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).</math>
 
 
* <math>\gcd\left(F_n,F_{n+1}\right)\ =\ \gcd\left(F_n,F_{n+2}\right)\ =\ 1</math>
 
Indeed,
 
::<math>\gcd\left(F_0,F_1\right)\ =\ \gcd\left(F_0,F_2\right)\ =\ 1</math>
 
and the rest is an easy induction.
 
 
* <math>F_n\ =\ F_{k+1}\cdot F_{n-k} + F_k\cdot F_{n-k-1}</math>
 
:for all integers <math>\ k,n,</math>&nbsp; such that <math>\ 0\le k < n.</math>
 
 
Indeed, the equality holds for <math>\ k=0,</math>&nbsp; and the rest is a routine induction on <math>\ k.</math>
 
Next, since <math>\gcd\left(F_k,F_{k+1}\right) = 1</math>,&nbsp; the above equality implies:
 
::: <math>\gcd\left(F_k,F_n\right)\ =\ \gcd\left(F_k,F_{n-k}\right)</math>
 
which, via Euclid algorithm, leads to:
 
 
*<math>\gcd(F_m, F_n)\ =\ F_{\gcd(m,n)} </math>
 
Let's note the two instant corollaries of the above statement:
 
 
*If <math>\ m</math>&nbsp; divides <math>\ n\ </math> then <math>\ F_m\ </math> divides <math>\ F_n\ </math>
 
*If <math>\ F_p\ </math>&nbsp; is a prime number different from 3, then <math>\ p</math>&nbsp; is prime. (The converse is false.)
 
== Algebraic identities ==
 
*<math>F_{n-1}\cdot F_{n+1}-F_n\,^2\ =\ (-1)^n\ </math> &nbsp; &nbsp; for n=1,2,...
*<math>\sum_{i=0}^n F_i\,^2\ =\ F_n \cdot F_{n+1}</math>
 
== Direct formula and the [[golden ratio]] ==
We have
:<math>F_n\ =\ \frac{1}{\sqrt{5}}\cdot \left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>
for every <math>\ n=0,1,\dots</math> .
 
Indeed, let&nbsp; <math>A := \frac{1+\sqrt{5}}{2}</math>&nbsp; and &nbsp;<math>a := \frac{1-\sqrt{5}}{2}</math> .&nbsp; Let
 
:<math>f_n\ :=\ \frac{1}{\sqrt{5}}\cdot(A^n - a^n)</math>
 
Then:
* <math>f_0 = 0\ </math> &nbsp; &nbsp; and &nbsp; &nbsp; <math>\ f_1 = 1</math>
* <math>A^2 = A+1\ </math> &nbsp; &nbsp; hence &nbsp; &nbsp; <math>\ A^{n+2} = A^{n+1}+A^n</math>
* <math>a^2 = a+1\ </math> &nbsp; &nbsp; hence &nbsp; &nbsp; <math>a^{n+2} = a^{n+1}+a^n\ </math>
* <math>f_{n+2}\ =\ f_{n+1}+f_n</math>
 
for every <math>\ n=0,1,\dots</math>. Thus <math>\ f_n = F_n</math>&nbsp; for every <math>\ n=0,1,\dots,</math> and the formula is proved.
 
Furthermore, we have:
 
* <math>A\cdot a = -1\ </math>
* <math>A > 1\ </math>
* <math>-1 < a < 0\ </math>
* <math>\frac{1}{2}\ >\ \left|\frac{1}{\sqrt{5}}\cdot a^n\right|\quad\rightarrow\quad 0</math>
 
It follows that
:<math>F_n\ </math>&nbsp; is the nearest integer to&nbsp; <math>\frac{1}{\sqrt{5}}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n</math>
 
for every <math>\ n=0,1,\dots</math> . The above constant <math>\ A</math>&nbsp; is known as the famous [[golden ratio]] <math>\ \Phi.</math>&nbsp; Thus:
 
:::<math>\Phi\ =\ \lim_{n\to\infty}\frac{F_{n+1}}{F_n}\ =\ \frac{1+\sqrt{5}}{2}</math>
 
== Fibonacci generating function ==
 
The '''Fibonacci generating function''' is defined as the sum of the following power series:
 
::<math>g(x)\ :=\ \sum_{n=0}^\infty F_n\cdot x^n</math>
 
The series is convergent for&nbsp; <math>\ |x|<\frac{1}{\Phi}.</math>&nbsp; Obviously:
 
::<math>g(x)\ =\ x+x\cdot g(x) + x^2\cdot g(x)\ </math>
 
hence:
 
:::<math>g(x)\ =\ \frac{x}{1-x-x^2}</math>


The sequence of fibonacci numbers was first used, to repesent the growth of a colony of rabbits, starting with one pair of rabbits.
Value <math>\ g(x)</math>&nbsp; is a rational number whenever ''x'' is rational. For instance, for ''x'' = &frac12;:


==Properties==
:<math>\frac{F_1}{2}+\frac{F_2}{4}+\frac{F_3}{8}+\cdots\ =\ 2</math>


*The quotient of two consecutive fibonacci numbers converges to the [[golden ratio]]: <math>\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\varphi</math>
and for ''x'' = &minus;&frac12; (after multiplying the equality by &minus;1):
*If <math>\scriptstyle m > 2\ </math> divides <math>\scriptstyle n\ </math> then <math>\scriptstyle F_m\ </math> divides <math>\scriptstyle F_n\ </math>
*If <math>\scriptstyle p \ge 5</math> is a prime number, then is <math>\scriptstyle F_p\ </math> also a prime number.
*<math>\operatorname{gcd}(f_m, f_n) = f_{\operatorname{gcd}(m,n)} </math>
*<math>F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 = \sum_{i=0}^n F_i^2 = F_n \cdot F_{n+1}</math>


==Further reading==
:<math>\frac{F_1}{2}-\frac{F_2}{4}+\frac{F_3}{8}-\cdots\ =\ \frac{2}{5}</math>
* [[John Horton Conway|John H. Conway]] und Richard K. Guy, ''The Book of Numbers'', ISBN 0-387-97993-X


[[Category:Mathematics Workgroup]]
== Further reading ==
* [[John Horton Conway|John H. Conway]] and Richard K. Guy, ''The Book of Numbers'', ISBN 0-387-97993-X[[Category:Suggestion Bot Tag]]

Latest revision as of 07:00, 16 August 2024

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

In mathematics, the Fibonacci numbers form a sequence in which the first number is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers in the series. In mathematical terms, it is defined by the following recurrence relation:


The sequence of Fibonacci numbers starts with : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

It was first used to represent the growth of a colony of rabbits, starting with a single pair of rabbits. It has applications in mathematics as well as other sciences, and is a popular illustration of recursive programming in computer science.

Divisibility properties

We will apply the following simple observation to Fibonacci numbers:

if three integers   satisfy equality   then


Indeed,

and the rest is an easy induction.


for all integers   such that


Indeed, the equality holds for   and the rest is a routine induction on

Next, since ,  the above equality implies:

which, via Euclid algorithm, leads to:


Let's note the two instant corollaries of the above statement:


  • If   divides then divides
  • If   is a prime number different from 3, then   is prime. (The converse is false.)

Algebraic identities

  •     for n=1,2,...

Direct formula and the golden ratio

We have

for every .

Indeed, let    and   .  Let

Then:

  •     and    
  •     hence    
  •     hence    

for every . Thus   for every and the formula is proved.

Furthermore, we have:

It follows that

  is the nearest integer to 

for every . The above constant   is known as the famous golden ratio   Thus:

Fibonacci generating function

The Fibonacci generating function is defined as the sum of the following power series:

The series is convergent for    Obviously:

hence:

Value   is a rational number whenever x is rational. For instance, for x = ½:

and for x = −½ (after multiplying the equality by −1):

Further reading