как "на пальцах" получить формулу для чисел Фибоначчи

[deep down]

Пытаюсь придумать, как получить формулы Бине человеку, который не знает линейной алгебры.
Пока приходят в голову только рояли в кустах и кролики в шляпах, например:
1. Решение однородного разностного уравнения первой степени - экспонента. А давайте и для второй её попробуем.
2. Попробуем свести к виду $x_{n+1}-2x_n=3(x_n-2x_{n-1})$ для снижения степени. Дальше всё прямолинейно, но сам шаг опять же далеко не очевиден.

Какие способы посоветуете?

[EtCetera]

А нужно именно получить формулу Бине или просто доказать ее справедливость? Непреднамеренно (конечно же) подглядев формулу, второе можно легко сделать по индукции.

[kp9r4d]

А зачем нужно знать линейную алгебру для вывода формулы Бине?

[Ms-dos4]

deep down в сообщении #876097 писал(а):

1. Решение однородного разностного уравнения первой степени - экспонента.

Кто сказал?

deep down в сообщении #876097 писал(а):

2. Попробуем свести к виду

$$x_{n+1}-2x_n=3(x_n-2x_{n-1})$$

для снижения степени. Дальше всё прямолинейно, но сам шаг опять же далеко не очевиден.

Ваше разностное уравнение вообще не имеет отношения к числам Фибоначчи

Как совет - либо получать через характеристическое уравнение, либо идти наоборот, начиная с $\[\varphi \]$ и $\[{\varphi ^{ - 1}}\]$.
P.S.Какое отношение линал имеет к разностным уравнениям?

[ewert]

Ms-dos4 в сообщении #876105 писал(а):

P.S.Какое отношение линал имеет к разностным уравнениям?

Ровно такое же, что и к линейным дифурам. Т.е. непосредственное. Другое дело, что изучать эти уравнения можно и без линала, но это -- не вполне приходя в сознание.

[Ms-dos4]

ewert
А, в этом смысле (я почему то подумал про непосредственную методику решения). Так если нужно просто объяснить кому то про формулу Бине, не обязательно излагать полную теорию. Дать как факт характеристическое уравнение и всё (если есть знание дифуров - провести параллели).

[nnosipov]

kp9r4d в сообщении #876104 писал(а):

А зачем нужно знать линейную алгебру для вывода формулы Бине?

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

[Padawan]

А что касается конкретных уравнений, то матрицу рекуррентного преобразования в $n$-тую степень можно даже без жордановой нормальной формы возводить. И получать выражение для $n$-того члена.

[deep down]

Ms-dos4 в сообщении #876105 писал(а):

Ваше разностное уравнение вообще не имеет отношения к числам Фибоначчи

Это просто был пример, чтобы потом попробовать разложить таким же образом соотношение для Фибоначчи

Ms-dos4 в сообщении #876105 писал(а):

либо получать через характеристическое уравнение, либо идти наоборот, начиная с $\[\varphi \]$ и $\[{\varphi ^{ - 1}}\]$.

В том всё и дело - и уравнение и постоянные золотого сечения будут кроликами из шляпы.
Если сказать - а вдруг экспонента какая-то подойдёт, то дальше путь очевиден. Естественным образом она может возникнуть из жорданового разложения, но это ни разу не элементарная теория. И желательно матрицы вообще не употреблять

[nnosipov]

deep down в сообщении #876165 писал(а):

И желательно матрицы вообще не употреблять

А кому это надо? Если студентам, то это просто вредно. Если школьникам, то есть популярные брошюры на эту тему и для них. Зачем здесь придумывать что-то эдакое?

-- Вт июн 17, 2014 00:20:15 --

deep down в сообщении #876165 писал(а):

Если сказать - а вдруг экспонента какая-то подойдёт, то дальше путь очевиден.

Почему бы и нет? Свойства геометрической прогрессии вполне вдохновляют.

[ИСН]

Это надо с пчёлок и цветочков начинать. Посмотрим на отношение двух последовательных чисел Ф. Ух ты, оно к чему-то сходится, да ещё как быстро! Ну-ка, а как бы найти...

[ewert]

nnosipov в сообщении #876150 писал(а):

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

Вполне возможно, если эту форму знать. Но необходимости в ней -- ни малейшей. "Сударыня, Вас обманули: Вам дали гораздо лучший мех"...

nnosipov в сообщении #876169 писал(а):

deep down в сообщении #876165 писал(а):

И желательно матрицы вообще не употреблять

А кому это надо? Если студентам, то это просто вредно.

Вот конкретно в этой теме -- категорически вредны именно матрицы. Линейноалгебраические соображения можно считать необходимыми (если хочется сознательности), но вот конкретно матрицы -- вредны без вариантов.

-- Пн июн 16, 2014 22:47:04 --

deep down в сообщении #876165 писал(а):

Если сказать - а вдруг экспонента какая-то подойдёт, то дальше путь очевиден.

Но это же вполне естественный подход, раз уж речь о разностных уравнениях. В конце концов, в дифурах мотивация ровно такая же. Для уравнения первого порядка экспонента очевидна со всех точек зрения; а для более высокого -- почему бы и не попробовать?... И тут вдруг выясняется (о, чудо!), что это даёт результат на 100%.

По крайней мере "в случаях общего положения"; ну а с нюансами можно разобраться и позже. Вот ровно так же и птички. (конечно, для приблизительно 100%-ности придётся привлекать линейноалгебраические вещи; но ни разу не матрицы)

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

[nnosipov]

ewert в сообщении #876197 писал(а):

Вполне возможно, если эту форму знать. Но необходимости в ней -- ни малейшей.

Не стоит мелочиться в данном случае. Мало ли в чём нет необходимости, это же не повод не обращать внимание на естественный подход.

ewert в сообщении #876197 писал(а):

Вот конкретно в этой теме -- категорически вредны именно матрицы.

В какой этой? Когда я говорил про матрицы, я имел в виду именно линейно-алгебраический подход. Если угодно, могу "матрица" заменить на "линейный оператор".

[ewert]

nnosipov в сообщении #876200 писал(а):

это же не повод не обращать внимание на естественный подход.

Так он здесь как раз и неестественен. Мало того, что жорданова форма -- это серьёзная (и неоправданная) морока, но и:

nnosipov в сообщении #876200 писал(а):

Когда я говорил про матрицы, я имел в виду именно линейно-алгебраический подход

-- Вы говорили совсем неправильно. Линейные операторы здесь идейны (безусловно), но матрицы для них совсем не обязательны. В очень многих случаях действие оператора очевидно, матрица же его -- лишь запудривает мозги, и явного её выписывания следует тщательно избегать. И это как раз ровно тот самый случай.

[notabene]

А зачем человеку, не знающему линейной алгебры формулы Бине?