Путеводитель для влюблённых в математику - Эдвард Шейнерман
Книгу Путеводитель для влюблённых в математику - Эдвард Шейнерман читаем онлайн бесплатно и без регистрации! Читать онлайн вы можете не только на компьютере, но и на андроид (Android), iPhone и iPad. Наслаждайтесь!
173 0 04:43, 26-05-2019
ЧИТАТЬ КНИГУ ОФЛАЙН в приложении android
Книга Путеводитель для влюблённых в математику - Эдвард Шейнерман читать онлайн бесплатно без регистрации
Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F0 до F5 дает:
F0 + F1 + F2 + F3 + F4 + F5 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F7 – 1.
Сложение чисел от F0 до F6 дает 33, что на единицу меньше F8 = 34. Мы можем записать формулу для неотрицательных целых чисел n:
F0 + F1 + F2 + … + Fn = Fn + 2–1. (*)
Вероятно, лично вам достаточно будет увидеть, что формула (*) работает в дюжине случаев, чтобы вы поверили, что она верна, но математики жаждут доказательств. Мы рады представить вам два возможных доказательства того, что она верна для всех неотрицательных целых чисел n. Первое называется доказательством по индукции, второе – комбинаторным доказательством.
Доказательство по индукции
Формула (*) представляет собой бесконечно много формул в свернутом виде. Доказать, что (*) верно для конкретного значения n, скажем для n = 6, – простая арифметическая задача. Достаточно будет записать числа от F0 до F6 и сложить их:
F0 + F1 + … + F6 = 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.
Несложно увидеть, что F8 = 34, поэтому формула действует.
Перейдем к F7. Не будем тратить время и складывать все числа: мы уже знаем сумму вплоть до F6. Таким образом,
(F0 + F1 + … + F6) + F7 = 33 + 21 = 54.
Как и раньше, все сходится: F9 = 55.
Если сейчас мы начнем проверять, работает ли формула для n = 8, наши силы окончательно иссякнут. Но все же посмотрим, что мы уже знаем и что хотим выяснить:
F0 + F1 + … + F7 = F9–1.F0 + F1 + … + F7 + F8 =?
Воспользуемся предыдущим результатом:
(F0 + F1 + … + F7) + F8 = (F9– 1) + F8.
Мы, конечно, можем вычислить (F9 – 1) + F8 арифметически. Но так мы устанем еще больше. В то же время мы знаем, что F8 + F9 = F10. Таким образом, нам не нужно ничего высчитывать или заглядывать в таблицу чисел Фибоначчи:
(F0 + F1 + … + F7) + F8 = (F9–1) + F8 = (F8 + F9) – 1 = F10– 1.
Мы удостоверились, что формула работает для n = 8, на основе того, что знали про n = 7.
В случае n = 9 мы точно так же опираемся на результат для n = 8 (убедитесь в этом самостоятельно). Разумеется, доказав верность (*) для n, мы можем быть уверены, что (*) верно и для n + 1.
Мы готовы дать полное доказательство. Как уже было сказано, (*) представляет собой бесконечное количество формул для всех значений n от нуля до бесконечности. Посмотрим, как работает доказательство.
Вначале мы доказываем (*) в простейшем случае, для n = 0. Мы просто проверяем, что F0 = F0 + 2 – 1. Так как F0 = 1, а F2 = 2, очевидным образом 1 = 2 – 1, а F0 = F2 – 1.
Дальше нам достаточно показать, что верность формулы для одного значения n (скажем, n = k) автоматически означает верность для n + 1 (в нашем примере n = k + 1). Нам лишь надо продемонстрировать, как устроено это «автоматически». Что нам нужно сделать?
Возьмем некоторое число k.
Предположим, мы уже знаем, что
F0 + F1 + … + Fk = Fk + 2– 1.
Мы ищем величину
F0 + F1 + … + Fk + Fk + 1.
Мы уже знаем сумму чисел Фибоначчи вплоть до Fk, поэтому у нас получается:
(F0 + F1 + … + Fk) + Fk + 1 = (Fk + 2–1) + Fk + 1.
Правая часть равна Fk + 2 – 1 + Fk + 1, и мы знаем, чему равна сумма следующих друг за другом чисел Фибоначчи:
Fk + 2–1 + Fk + 1 = (Fk + 2 + Fk + 1) – 1 = Fk + 3– 1
Подставим в наше равенство:
(F0 + F1 + … + Fk) + Fk + 1 = Fk + 3– 1
Сейчас я объясню, что мы сделали. Если мы знаем, что (*) верно, когда мы суммируем числа вплоть до Fk, тогда (*) должно быть верно, если мы приплюсуем Fk + 1.
Подытожим:
• Формула (*) верна для n = 0.
• Если формула (*) верна для n, она верна и для n + 1.
Мы можем уверенно сказать, что (*) верно для любых значений n. Верно ли (*) для n = 4987? Это так, если выражение верно для n = 4986, что основано на верности выражения для n = 4985, и так далее до n = 0. Следовательно, формула (*) верна для всех возможных значений n.
Этот метод доказательства известен под названием математическая индукция (или доказательство по индукции). Мы проверяем базовый случай и даем шаблон, по которому каждый следующий случай может быть доказан на основе предыдущего.
Комбинаторное доказательство
Прочитали книгу? Предлагаем вам поделится своим впечатлением! Ваш отзыв будет полезен читателям, которые еще только собираются познакомиться с произведением.
Уважаемые читатели, слушатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.
Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации. Просьба отказаться от оскорблений, угроз и запугиваний. Просьба отказаться от нецензурной лексики. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.
Надеемся на Ваше понимание и благоразумие. С уважением, администратор сайта
Оставить комментарий
Mkot1312 июль 21:17
