Викия

Математика

Числа Фибоначчи

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Чи́сла Фибона́ччипоследовательность целых чисел \left\{F_n\right\}, заданная с помощью рекуррентного соотношения

F_0 = 0,\quad F_1 = 1,\quad F_{n+1} = F_n + F_{n-1}  .

Последовательность чисел Фибоначчи начинается так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 … (последовательность A000045 в OEIS)

Иногда числа Фибоначчи рассматривают и для неположительных номеров n. Ряд, соответствующий определению чисел Фибоначчи \left(F_n=F_{n-1}+F_{n-2}\right): …, −55, 34, −21, 13, −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, …

<tr><th>F_n</td><td>-55</td><td>34</td><td>-21</td><td>13</td><td>-8</td><td>5</td><td>-3</td><td>2</td><td>-1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>2</td><td>3</td><td>5</td><td>8</td><td>13</td><td>21</td><td>34</td><td>55</td></tr> </table> Легко видеть, что F_{-n} = (-1)^{n+1}F_n. Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств (но не все!).

Формула Бине Править

Формула Бине выражает в явном виде значение F_n как функцию от n:

F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}},

где \phi=\frac{1 + \sqrt{5}}{2} — золотое сечение. При этом \phi\,\! и (-\phi )^{-1}=1-\phi\,\! являются корнями квадратного уравнения x^2-x-1=0\,\!.

Из формулы Бине следует, что для всех n\ge0, F_n есть ближайшее к \frac{\phi^n}{\sqrt{5}}\, целое число, то есть F_n = \left\lfloor\frac{\phi^n}{\sqrt{5}}\right\rceil. В частности, справедлива асимптотика F_n\sim \frac{\phi^n}{\sqrt{5}}.

Тождества Править

  • F_1+F_2+F_3+\dots+F_n=F_{n+2}-1
  • F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}
  • F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1
  • F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}
  • F_{n+1}F_{n+2}^{}-F_nF_{n+3}=(-1)^{n+1}
  • F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1}
  • F_n^2+F_{n+1}^2=F_{2n+1}
  • Числа Фибоначчи представляются значениями континуант на наборе единиц: F_n = K_n(1,\dots,1), то есть
F_n =
\det \begin{pmatrix} 
1 & 1    & 0 &\cdots & 0 \\ 
-1  & 1  & 1 &  \ddots    & \vdots\\
0   & -1   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & 1 \\ 
0 & \cdots & 0 & -1 & 1
\end{pmatrix}, а также \ F_{n+1} =
\det \begin{pmatrix} 
1 & i    & 0 &\cdots & 0 \\ 
i  & 1  & i &  \ddots    & \vdots\\
0   & i   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & i \\ 
0 & \cdots & 0 & i & 1\end{pmatrix},
где матрицы имеют размер n\times n, i — мнимая единица.
  • Для любого n,
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
       \begin{pmatrix} F_{n+1} & F_n \\
                       F_n   & F_{n-1} \end{pmatrix}.
Эта формула даёт быстрый алгоритм вычисления чисел Фибоначчи.
(-1)^n = F_{n+1} F_{n-1} - F_n^2

Свойства Править

  • Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (F_m,F_n) = F_{(m,n)}. Следствия:
    • F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n=2). В частности, F_m делится на F_3=2 (то есть является чётным) только для m=3k; F_m делится на F_4=3 только для m=4k; F_m делится на F_5=5 только для m=5k и т. д.
    • F_m может быть простым только для простых m (с единственным исключением m=4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — F_{19}=4181=37\cdot 113. Неизвестно, бесконечное ли количество чисел Фибоначчи являющихся простыми.
F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} {n-k\choose k}.
  • В 1964 J. H. E. Cohn доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F_0=0^2=0, F_1=1^2=1, F_2=1^2=1, F_{12}=12^2=144. При этом для n=0,1,12 верно утверждение F_n=n^2.
0 + x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}
  • Множество чисел Фибоначчи совпадает с множеством положительных значений полинома
z = 2xy^4 + x^2 y^3 - 2 x^3 y^2 - y^5 -  x^4 y + 2y,

на множестве неотрицательных целых чисел x и y (P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, p.193).

  • Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
  • Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60. Если от каждого числа брать по две последние цифры, то они образуют последовательность с периодом, равным 300. Если брать по три последние цифры — с периодом 1500, по четыре — с периодом 15000, по пять — с периодом 150000, по шесть — с периодом 1500000.

См. также Править

Литература Править

Ссылки Править

bg:Число на Фибоначи bn:ফিবোনাচ্চি রাশিমালা bs:Fibonaccijev broj ca:Successió de Fibonacci cs:Fibonacciho posloupnost da:Fibonacci-talel:Ακολουθία Φιμπονάτσιeo:Fibonaĉi-nombrojeu:Fibonacciren zenbakiakhe:סדרת פיבונאצ'י hi:हेमचन्द्र श्रेणी hr:Fibonaccijev broj hu:Fibonacci-számok id:Bilangan Fibonaccilt:Fibonačio skaičius lv:Fibonači skaitļi nl:Rij van Fibonacci no:Fibonacci-tall pl:Ciąg Fibonacciegoscn:Succissioni di Fibonacci sk:Fibonacciho postupnosť sl:Fibonaccijevo število sr:Фибоначијев низ sv:Fibonaccital ta:ஃபிபனாச்சி எண்கள் th:เลขฟีโบนัชชีuk:Послідовність Фібоначчі vi:Dãy Fibonacci vls:Reke van Fibonacci

Викия-сеть

Случайная вики
n</td><td>-10</td><td>-9</td><td>-8</td><td>-7</td><td>-6</td><td>-5</td><td>-4</td><td>-3</td><td>-2</td><td>-1</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td>