|
В общем, имеется числовая последовательность u_n, у которой каждый следующий член вычисляется как сумма двух предыдущих, то есть u_n = u_(n−1) + u_(n+2). Так же известны значения u_n для нескольких первых значений n. Как найти (вывести) общую формулу для u_n, которая позволяла бы по номеру n последовательности u_n вычислить, чему равно значение u_n. Например, такая последовательно: 1, 1, 2, 3, 5, 8, 13... и так далее, здесь каждый член такой последовательности равен сумме двух предыдущих членов, то есть как раз формула u_n = u_(n−1) + u_(n+2). Чему будет равен 1000 член такой последовательности? задан 4 Янв '14 2:33 
Inna |
|
Если речь идёт о последовательности Фибоначчи, где каждый следующий член равен сумме двух предыдущих, то рекуррентная формула должна иметь вид $%u_n=u_{n−1}+u_{n-2}$%. Формула общего члена в этом случае хорошо известна -- это так называемая формула Бине, выведенная в 40-х годах XIX века: $$a_n=\frac{\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n}{\sqrt5}.$$ Ввиду того, что $%n$%-я степень числа $%\frac{1-\sqrt5}2$% стремится к нулю, за $%a_n$% можно принять ближайшее целое к числу $%q^n/\sqrt5$%, где $%q=\frac{1+\sqrt5}2$%. То есть фактически здесь присутствует геометрическая прогрессия, члены которой округляются до целых чисел. Число $%a_{1000}$% в десятичной записи имеет такой вид (все цифры идут подряд): 4346655768693745643568852767504062580256466051737178040248172908953655541794905 1890403879840079255169295922593080322634775209689623239873322471161642996440906 533187938298969649928516003704476137795166849228875 отвечен 4 Янв '14 3:00 
falcao Добавлю ссылку на М. Холл. Комбинаторика. М.: Мир - 1970 (с. 38)
(4 Янв '14 3:07)
Urt
|
Поскольку у меня не хватает кармы для комментариев, добавлю здесь ссылку на один из возможных выводов формулы из ответа @falcao: http://hashcode.ru/questions/269280#269588 (смотрите вторую половину ответа).
PS: Кто-нибудь, превратите, пожалуйста, в комментарий.