imported>Paul Wormer |
|
(3 intermediate revisions by 2 users not shown) |
Line 1: |
Line 1: |
| {{subpages}} | | {{subpages}} |
|
| |
|
| In mathematics, the '''Fibonacci numbers''' form a [[sequence]] in which the first number in the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers. In mathematical terms, it is 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 12: |
Line 12: |
|
| |
|
|
| |
|
| The sequence of Fibonacci numbers starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... | | The sequence of Fibonacci numbers starts with : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... |
|
| |
|
| The sequence of Fibonacci numbers was first used to represent the growth of a colony of rabbits, starting with a single pair of rabbits.
| | 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== | | ==Divisibility properties== |
Line 116: |
Line 116: |
|
| |
|
| == 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]] |
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:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00008893a71eebbf4e7d89a0c162fe6359f5ac8c)
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
![{\displaystyle \ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe1f82cbf2226190742b09093e29ac452641b288)
![{\displaystyle \gcd \left(F_{n},F_{n+1}\right)\ =\ \gcd \left(F_{n},F_{n+2}\right)\ =\ 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51c297f4b91a052a7d085403967d996e3bddff0e)
Indeed,
![{\displaystyle \gcd \left(F_{0},F_{1}\right)\ =\ \gcd \left(F_{0},F_{2}\right)\ =\ 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49e543d214867aa0fa8a655868503e75ca70db94)
and the rest is an easy induction.
![{\displaystyle F_{n}\ =\ F_{k+1}\cdot F_{n-k}+F_{k}\cdot F_{n-k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c56dbbf64bc6a2a24d305387effe371a0dd3a5c0)
- for all integers
such that ![{\displaystyle \ 0\leq k<n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c636a6f01410974e163c0eb0bc4b7e32957252d6)
Indeed, the equality holds for
and the rest is a routine induction on
Next, since
, the above equality implies:
![{\displaystyle \gcd \left(F_{k},F_{n}\right)\ =\ \gcd \left(F_{k},F_{n-k}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21c9e1b6f394d1e5dbc622983c9f2fdd5a9def7c)
which, via Euclid algorithm, leads to:
![{\displaystyle \gcd(F_{m},F_{n})\ =\ F_{\gcd(m,n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/509a36e793991216a9af4617b4efcb1e1ebe27fc)
Let's note the two instant corollaries of the above statement:
- If
divides
then
divides ![{\displaystyle \ F_{n}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/53f64aac3251d0ee585a0f71f447fcecafc51476)
- If
is a prime number different from 3, then
is prime. (The converse is false.)
Algebraic identities
for n=1,2,...
![{\displaystyle \sum _{i=0}^{n}F_{i}\,^{2}\ =\ F_{n}\cdot F_{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca62199a40d446eb19d0d3e98eb13a738e2974b8)
We have
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a91a8b5d28fd30b9fe698327c3483f77be546519)
for every
.
Indeed, let
and
. Let
![{\displaystyle f_{n}\ :=\ {\frac {1}{\sqrt {5}}}\cdot (A^{n}-a^{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cdacf5074f5560a0aa14ef534782b08de4f8011)
Then:
and ![{\displaystyle \ f_{1}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c754577bc3a87fedb269c17aa0a4afd510954174)
hence ![{\displaystyle \ A^{n+2}=A^{n+1}+A^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2d6a827b03e84581e3473bf1e4b87934f3fe79e)
hence ![{\displaystyle a^{n+2}=a^{n+1}+a^{n}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c521491bf1e404a03afaede928e51d6bc7890dfc)
![{\displaystyle f_{n+2}\ =\ f_{n+1}+f_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b9a2928ddeaa5a041ae0e96cf0ae8bf57d987dc)
for every
. Thus
for every
and the formula is proved.
Furthermore, we have:
![{\displaystyle A\cdot a=-1\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6e67289e80bb0012bf18aa45e39153cd61d4553)
![{\displaystyle A>1\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bd1c3643c485dcaca05621ea6056995752259f2)
![{\displaystyle -1<a<0\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ed51d0637826bf787277dfbab290b1edc0ece29)
![{\displaystyle {\frac {1}{2}}\ >\ \left|{\frac {1}{\sqrt {5}}}\cdot a^{n}\right|\quad \rightarrow \quad 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0b44c516a34da87eb8a4ff4b72d49472efbbb21)
It follows that
is the nearest integer to ![{\displaystyle {\frac {1}{\sqrt {5}}}\cdot \left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07bfffce67fac19c1ffa5ee311cdc6d400c2e587)
for every
. The above constant
is known as the famous golden ratio
Thus:
![{\displaystyle \Phi \ =\ \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}\ =\ {\frac {1+{\sqrt {5}}}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3a88a8256abc1bf972c5d14ea915ef8b535edf)
Fibonacci generating function
The Fibonacci generating function is defined as the sum of the following power series:
![{\displaystyle g(x)\ :=\ \sum _{n=0}^{\infty }F_{n}\cdot x^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7c0a51099ee54bddc3501650edc379e47e2a47c)
The series is convergent for
Obviously:
![{\displaystyle g(x)\ =\ x+x\cdot g(x)+x^{2}\cdot g(x)\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/874b82f8b9f8d6d75f3c406070841a237ee5fe1f)
hence:
![{\displaystyle g(x)\ =\ {\frac {x}{1-x-x^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042cc37c1665bcdaa005f852f24d33acaf04cfed)
Value
is a rational number whenever x is rational. For instance, for x = ½:
![{\displaystyle {\frac {F_{1}}{2}}+{\frac {F_{2}}{4}}+{\frac {F_{3}}{8}}+\cdots \ =\ 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27020a4d095b53d84e52b60038a2de97243aadaf)
and for x = −½ (after multiplying the equality by −1):
![{\displaystyle {\frac {F_{1}}{2}}-{\frac {F_{2}}{4}}+{\frac {F_{3}}{8}}-\cdots \ =\ {\frac {2}{5}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3429d677b7ea017ebc7f827eedb6ee7b6a8faa35)
Further reading