Fibonacci number: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Aleksander Stos
(→‎Properties: unfortunately it's false that way :( otherwise, I'd easily claim $100K right now... see http://w2.eff.org/awards/coop.php)
mNo edit summary
 
(33 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{subpages}}
{{subpages}}
<!-- Taken from en.wikipedia.org/wiki/Fibonacci number -->
 
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 10: 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>


The sequence of fibonacci numbers was first used, to repesent the growth of a colony of rabbits, starting with one pair of rabbits.


==Properties==
* <math>\gcd\left(F_n,F_{n+1}\right)\ =\ \gcd\left(F_n,F_{n+2}\right)\ =\ 1</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>
Indeed,
*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> and <math>\scriptstyle F_p\ </math> is a prime number then <math>p</math> is prime. (The converse is false.)
*<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>


== Direct formula ==
::<math>\gcd\left(F_0,F_1\right)\ =\ \gcd\left(F_0,F_2\right)\ =\ 1</math>


Let&nbsp; <math>A := \frac{1+\sqrt{5}}{2}</math>&nbsp; and &nbsp;<math>a := \frac{1-\sqrt{5}}{2}</math> .&nbsp; Let
and the rest is an easy induction.


:::<math>f_n\ :=\ \frac{1}{\sqrt{5}}\cdot(A^n - a^n)</math>
 
* <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:
Then:
Line 38: Line 77:
* <math>f_{n+2}\ =\ f_{n+1}+f_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> , i.e.
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.


<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>
Furthermore, we have:
 
for every <math>\ n=0,1,\dots</math> . Furthermore:


* <math>A\cdot a = -1\ </math>
* <math>A\cdot a = -1\ </math>
Line 49: Line 86:
* <math>\frac{1}{2}\ >\ \left|\frac{1}{\sqrt{5}}\cdot a^n\right|\quad\rightarrow\quad 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 ==


It follows that
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>
 
Value <math>\ g(x)</math>&nbsp; is a rational number whenever ''x'' is rational. For instance, for ''x'' = &frac12;:


<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>
:<math>\frac{F_1}{2}+\frac{F_2}{4}+\frac{F_3}{8}+\cdots\ =\ 2</math>


for every <math>\ n=0,1,\dots</math> . It follows that&nbsp; <math>\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=A</math>;&nbsp; thus the value of the golden ratio is
and for ''x'' = &minus;&frac12; (after multiplying the equality by &minus;1):


::<math>\ \varphi\ =\ A\ =\ \frac{1+\sqrt{5}}{2}</math> .
:<math>\frac{F_1}{2}-\frac{F_2}{4}+\frac{F_3}{8}-\cdots\ =\ \frac{2}{5}</math>


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

Latest revision as of 06:00, 16 August 2024

This article is a stub and thus not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Fibonacci_number&printable=yes
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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n := \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{if } n > 1. \\ \end{cases} }


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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,b,c,}   satisfy equality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c = a+b,}   then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).}


  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_n,F_{n+1}\right)\ =\ \gcd\left(F_n,F_{n+2}\right)\ =\ 1}

Indeed,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_0,F_1\right)\ =\ \gcd\left(F_0,F_2\right)\ =\ 1}

and the rest is an easy induction.


  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n\ =\ F_{k+1}\cdot F_{n-k} + F_k\cdot F_{n-k-1}}
for all integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k,n,}   such that


Indeed, the equality holds for   and the rest is a routine induction on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k.}

Next, since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_k,F_{k+1}\right) = 1} ,  the above equality implies:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_k,F_n\right)\ =\ \gcd\left(F_k,F_{n-k}\right)}

which, via Euclid algorithm, leads to:


  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(F_m, F_n)\ =\ F_{\gcd(m,n)} }

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


  • If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m}   divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n\ } then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F_m\ } divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F_n\ }
  • If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F_p\ }   is a prime number different from 3, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p}   is prime. (The converse is false.)

Algebraic identities

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{n-1}\cdot F_{n+1}-F_n\,^2\ =\ (-1)^n\ }     for n=1,2,...
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^n F_i\,^2\ =\ F_n \cdot F_{n+1}}

Direct formula and the golden ratio

We have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)}

for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots} .

Indeed, let  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A := \frac{1+\sqrt{5}}{2}}   and  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a := \frac{1-\sqrt{5}}{2}} .  Let

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n\ :=\ \frac{1}{\sqrt{5}}\cdot(A^n - a^n)}

Then:

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_0 = 0\ }     and     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f_1 = 1}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^2 = A+1\ }     hence     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A^{n+2} = A^{n+1}+A^n}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^2 = a+1\ }     hence     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{n+2} = a^{n+1}+a^n\ }
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{n+2}\ =\ f_{n+1}+f_n}

for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots} . Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f_n = F_n}   for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots,} and the formula is proved.

Furthermore, we have:

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\cdot a = -1\ }
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A > 1\ }
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1 < a < 0\ }
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}\ >\ \left|\frac{1}{\sqrt{5}}\cdot a^n\right|\quad\rightarrow\quad 0}

It follows that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n\ }   is the nearest integer to  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{5}}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n}

for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots} . The above constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A}   is known as the famous golden ratio Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Phi.}   Thus:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi\ =\ \lim_{n\to\infty}\frac{F_{n+1}}{F_n}\ =\ \frac{1+\sqrt{5}}{2}}

Fibonacci generating function

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)\ :=\ \sum_{n=0}^\infty F_n\cdot x^n}

The series is convergent for  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |x|<\frac{1}{\Phi}.}   Obviously:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)\ =\ x+x\cdot g(x) + x^2\cdot g(x)\ }

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

Retrieved from "https://citizendium.org/wiki/index.php?title=Fibonacci_number&oldid=971927"