Решение упражнения 1.13 из SICP
Итак, нам требуется доказать, что Fib(n) – это ближайшее целое число к φn/√5, где φ=(1+√5)/2.
Для этого покажем две вещи:
- Fib(n) = (φn-ψn)/√5, где ψ=(1-√5)/2;
- (φn-ψn)/√5 – ближайшее целое число к φn/√5.
Приступим к первой части доказательства.
В первую очередь отметим, что
φ² = ((1+√5)/2)² = (1+2√5+5)/4 = (3+√5)/2 = 1+(1+√5)/2 = 1+φ,
ψ² = ((1-√5)/2)² = (1-2√5+5)/4 = (3-√5)/2 = 1+(1-√5)/2 = 1+ψ.
Далее проведем доказательство по индукции.
Проверим базу индукции для n=0 и n=1:
Fib(0) = 0 = (1-1)/√5 = (φ0-ψ0)/√5,
Fib(1) = 1 = √5/√5 = ((1+√5)/2-(1-√5)/2)/√5 = (φ¹-ψ¹)/√5.
Теперь предположим, что Fib(k) = (φk-ψk)/√5 для всех k от 0 до n и докажем это равенство при k=n+1.
Fib(n+1) = Fib(n) + Fib(n-1) = (φn-ψn)/√5 + (φn-1-ψn-1)/√5 = [φn-1(φ+1) – ψn-1(ψ+1) ]/√5 = (φn-1φ² – ψn-1ψ²)/√5 = (φn+1 – ψn+1)/√5.
Тем самым согласно принципу математической индукции Fib(n) = (φn-ψn)/√5 для всех целых неотрицательных n. Следовательно первая часть доказательства завершена.
Перейдем ко второй части доказательства, а именно докажем, что (φn-ψn)/√5 – ближайшее целое число к φn/√5. Сначала отметим, что (φn-ψn)/√5 является целым числом, так как равно числу Фибоначчи (согласно предыдущей части). Для того, чтобы оно было ближайшим целым к φn/√5, достаточно, чтобы |ψn|/√5 было всегда меньше ½. Покажем это, вновь воспользовавшись методом математической индукции.
База индукции. Проверим, что |ψ0/√5| < ½:
|ψ0/√5| = 1/√5 < 1/2 (так как √5>2).
Теперь в предположении, что |ψn/√5| < ½ покажем, что |ψn+1/√5| < ½:
|ψn+1/√5| = |ψψn/√5| = |(1-√5)/2| * |ψn/√5|.
Оценим каждый из сомножителей сверху:
1) 2 < √5 < 3 => -2 > -√5 > -3 => -1 > 1-√5 > -2 => -1/2 > (1-√5)/2 > -1 => |(1-√5)/2| < 1;
2) |ψn/√5| < 1/2 по предположению матиндукции.
Но тогда произведение сомножителей можно оценить сверху произведением их верхних оценок, то есть
|ψn+1/√5| = |(1-√5)/2| * |ψn/√5| < 1*½ = ½,
что и требовалось доказать.
Таким образом вторая часть, а с ней и все доказательство закончены.
Очень полезное упражнение, демонстрирующее мощь метода математической индукции в применении к задачам теории чисел.
Comments
Comment from Ar
Date: August 20, 2008, 5:20 pm
Уважаемый автор, мощь метода математической индукции огромна, но разве её нужно настолько здесь задействовать? Для доказательства факта (*): модуль пси в степени n, поделенный на корень из пяти, меньше одной второй, достаточно доказать два неравенства:
1. Корень из пяти больше двух ( нетрудно ;-)))))))))))))) )
2. Модуль пси в степени n меньше единицы. Это следует из того, что модуль пси меньше единицы. (Не многим труднее (1) 😉 )
В общем, факт (*) попросту очевиден…
Comment from Sergey Khenkin
Date: August 21, 2008, 7:52 am
Нда… Анекдот вспомнился:
Советское время, партийная верхушка, товарищ Сталин, режиссер, вся съемочная группа, актеры и т.д. собрались в кинотеатре, для того чтобы Сталин посмотрел фильм и одобрил для проката по стране.
Заканчивается фильм, тишина полная, все напряжены, ждут.
Сталин тихо говорит:
– Пачему у главного актера усы как у таварища Сталина? Расстрелять актера,.. режиссера… всю съемочную группу,.. министра культуры…
Бледный как мел режиссер спрашивает Сталина:
– Иосиф Виссарионович, а может сбрить усы главному герою???
Сталин, подумав:
– Ну или так.
В общем, или так 🙂
Comment from Ar
Date: August 22, 2008, 8:48 am
Спасибо за анекдот 🙂 Если можно, вопрос не про задачу: у Вас в разделе “связаться со мной” сказано “буду рад ответить”. Можно ли это счесть разрешением задавать вопросы касательно Scheme по e-mail? У меня упражнения из SICP идут нормально, но стоит подумать о небольших модификациях, и уже не знаю, как их делать 🙁 …
Comment from sindikat
Date: December 17, 2009, 2:14 pm
Вот как решил эту задачу я. Скажите, правильно ли это?
Сначала доказал, что (φ^n – ψ^n) / √5 равен 0 при n=0 и равен 1 при n=1.
Затем вывел такую формулу:
(φ^n – ψ^n) / √5 = (φ^n-1 – ψ^n-1) / √5 + (φ^n-2 – ψ^n-2) / √5 — по определению функции Фибоначчи.
Перенёс правую часть уравнения влево, извлёк общие множители:
(φ^n – ψ^n – φ^n-1 + ψ^n-1 – φ^n-2 + ψ^n-2) / √5 = (φ^n-2 * (φ^2 – φ – 1) – ψ^n-2 * (ψ^2 – ψ – 1)) / √5 = 0
Осталось вычислить (φ^2 – φ – 1) и (ψ^2 – ψ – 1), которые оказались равны нулю.
(φ^n-2 * 0 – ψ^n-2 * 0) / √5 = 0 — тождество.
ЧТД
Comment from qwe
Date: September 3, 2010, 9:51 pm
Эм, а как я должен догадаться, что
ψ² = 1+ψ.
?
Про φ аналогичное свойство написано в книге, а про ψ что-то нифига не понял… это же даже не золотое сечение (http://upload.wikimedia.org/math/a/9/c/a9cf8be89bb10d71d29934044de38239.png), но свойство золотого сечения для него выполняется. Ничего не понимаю.
Comment from Юра
Date: January 23, 2012, 11:44 pm
@qwe
ψ и φ корни квадратного уравнения x² = 1+ x
Comment from Александр
Date: July 23, 2012, 10:18 pm
большое спасибо, отличное решение
Comment from Evgeniy
Date: November 20, 2013, 12:09 pm
Самое интересное, что эта задачка делает в этой главе, и вообще книге? Ей же в книгу по дискретной математике самая дорога.
Comment from carrauntoohil
Date: February 10, 2022, 6:49 pm
Можно посмотреть в Википедии статью про числа фибоначчи, там приводится формула Бине, которая выражает в явном виде значение {\displaystyle F_{n}}F_{n} как функцию от n.
Она выводится с помощью уравнения {\displaystyle x^{2}-x-1=0.}x^{2}-x-1=0.
Write a comment