Fibonacci number: Difference between revisions
imported>Aleksander Stos m (math formula is universal) |
mNo edit summary |
||
(13 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In mathematics, the '''Fibonacci numbers''' form a [[sequence]] in which the first number | 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, ... | ||
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: | We will apply the following simple observation to Fibonacci numbers: | ||
Line 57: | Line 57: | ||
*If <math>\ F_p\ </math> is a prime number different from 3, then <math>\ p</math> is prime. (The converse is false.) | *If <math>\ F_p\ </math> is a prime number different from 3, then <math>\ p</math> is prime. (The converse is false.) | ||
== Algebraic identities == | |||
*<math>\sum_{i=0}^n F_i^2 = F_n \cdot F_{n+1}</math> | *<math>F_{n-1}\cdot F_{n+1}-F_n\,^2\ =\ (-1)^n\ </math> 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]] == | == Direct formula and the [[golden ratio]] == | ||
Line 89: | Line 91: | ||
for every <math>\ n=0,1,\dots</math> . The above constant <math>\ A</math> is known as the famous [[golden ratio]] <math>\ \Phi.</math> Thus: | for every <math>\ n=0,1,\dots</math> . The above constant <math>\ A</math> is known as the famous [[golden ratio]] <math>\ \Phi.</math> Thus: | ||
:::<math>\Phi\ =\ \lim_{n\to\infty}\frac{ | :::<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 <math>\ |x|<\frac{1}{\Phi}.</math> 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> is a rational number whenever ''x'' is rational. For instance, for ''x'' = ½: | |||
:<math>\frac{F_1}{2}+\frac{F_2}{4}+\frac{F_3}{8}+\cdots\ =\ 2</math> | |||
and for ''x'' = −½ (after multiplying the equality by −1): | |||
:<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]] | * [[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
![](http://s9.addthis.com/button1-share.gif)
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
- John H. Conway and Richard K. Guy, The Book of Numbers, ISBN 0-387-97993-X