Решение упражнения 1.13 из SICP

20 August, 2007 (19:20) | Решения упражнений

Итак, нам требуется доказать, что Fib(n) – это ближайшее целое число к φn/√5, где φ=(1+√5)/2.

Для этого покажем две вещи:

  1. Fib(n) = (φnn)/√5, где ψ=(1-√5)/2;
  2. nn)/√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 = (φ00)/√5,
Fib(1) = 1 = √5/√5 = ((1+√5)/2-(1-√5)/2)/√5 = (φ¹-ψ¹)/√5.

Теперь предположим, что Fib(k) = (φkk)/√5 для всех k от 0 до n и докажем это равенство при k=n+1.

Fib(n+1) = Fib(n) + Fib(n-1) = (φnn)/√5 + (φn-1n-1)/√5 = [φn-1(φ+1) – ψn-1(ψ+1) ]/√5 = (φn-1φ² – ψn-1ψ²)/√5 = (φn+1 – ψn+1)/√5.

Тем самым согласно принципу математической индукции Fib(n) = (φnn)/√5 для всех целых неотрицательных n. Следовательно первая часть доказательства завершена.

Перейдем ко второй части доказательства, а именно докажем, что (φnn)/√5 – ближайшее целое число к φn/√5. Сначала отметим, что (φnn)/√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

Самое интересное, что эта задачка делает в этой главе, и вообще книге? Ей же в книгу по дискретной математике самая дорога.

Write a comment