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

[brother]

Для общего развития интересуюсь
Числа Фибоначчи можно представить в виде какой-нибудь функции выражаемой в элементарных? Или представление данного ряда возможно только аналитическое?

[ИСН]

А крокодил - он зелёный или длинный?

[brother]

(Оффтоп)

И то и другое)))

[ИСН]

А почему же Вы тогда употребляете понятия "элементарное" и "аналитическое" как антонимы?

[brother]

Видимо дело в употреблении терминов не совсем осознавая их смысл. Под аналитическим я понимаю запись $a_n=a_{n-1}+a_{n-2}, n>2, a_1=a_2=1$, а под функцией выражаемой в элементарных я понимаю выражение содержащее показательные, тригонометрические, логарифмы, полиномы

[gris]

А я подумал, что имеется в виду аналитическое продолжение формулы Бине на комплексную плоскость. Кстати, эта формула выражена в элементарных функциях. Возведение положительного числа в степень можно выразить через стандартную экспоненту и логарифм.

Хотя там есть возведение отрицательного числа. Придётся какой-то сигнум использовать, а это не элементарная функция (в узком понимании).

[Joker_vD]

brother
Вы имеете в виду формулу для чисел Фибоначчи замкнутой форме, т.е.

$$F_n = \frac{\left(\frac{1 + \sqrt5}{2}\right)^n - \left(\frac{1 - \sqrt5}{2}\right)^n}{\sqrt5}?$$

[blondinko]

Joker_vD,
а меня вот всё время интересовало: зачем эту формулу всегда записывают в таком архи-неудобном представлении, вместо того чтобы разложить по биному и получить более-менее целочисленный вид, например такой?

$$\frac{1}{2^{n-1}}\sum\limits_{k=1}^{[\frac{n}{2}]} C_n^{2k-1}5^{k-1}$$

[ИСН]

Кому что удобнее. В таком виде не видна асимптотика.

[venco]

ИСН в сообщении #455608 писал(а):

В таком виде не видна асимптотика.

И на калькуляторе считать не удобно.

[nnosipov]

Ещё один аргумент в пользу формулы Бине таков. Допустим, нам нужно найти остаток $r$ от деления $n$-го числа Фибоначчи $F_n$ на некоторое натуральное $m$, при этом $n$ и $m$ очень велики (какие-нибудь 100-значные числа). Никакой надежды вычислить само число $F_n$ нет, однако остаток $r$ можно найти достаточно быстро. И здесь помогает именно формула Бине.

[ИСН]

Да, но только тут надо корень понимать соответственно.

[brother]

Joker_vD в сообщении #455582 писал(а):

brother
Вы имеете в виду формулу для чисел Фибоначчи замкнутой форме, т.е.

$$F_n = \frac{\left(\frac{1 + \sqrt5}{2}\right)^n - \left(\frac{1 - \sqrt5}{2}\right)^n}{\sqrt5}?$$

О, да! неужели меня поняли))) спасибо))) осталось понять как ее вывести, не говорите, пожалуйста, хочу сам

[ewert]

brother в сообщении #455843 писал(а):

не говорите, пожалуйста, хочу сам

ни за что не скажу, я же не зверь. Разве что подскажу: гуглите, например, на "разностные уравнения".

[brother]

gris в сообщении #455566 писал(а):

Придётся какой-то сигнум использовать, а это не элементарная функция (в узком понимании).

А, по-моему, элементарная))) Я думаю, пора бы уже интегралы Френеля (интегральный синус, косинус, логарифм) к элементарным функциям отнести (просто нас учат, что элементарные - это список функций перечисленных в сообщении выше) и даже модуль (!) не относят к элементарным функциям, не понимаю с чем это связано. А про интегралы Френеля пришла идея потому, что тригонометрические функции то тоже нужно приближенно вычислять, так и более современные калькуляторы можно научить считать эти функции. А вы (все) как считаете?