|
|
 |
Условие
а) Докажите, что в последовательности чисел Фибоначчи при m ≥ 2 встречается не менее четырёх и не более пяти m-значных чисел.
б) Докажите, что число F5n+2 (n ≥ 0) содержит в своей десятичной записи не менее n + 1 цифры.
Подсказка
Докажите сначала вспомогательные неравенства Fn+5 ≥ 10,5 Fn, Fn+4 ≤ 8Fn.
Решение
Заметим, что Fn ≤ Fn+1 ≤ 2Fn. Поэтому Fn+4 = Fn+3 + Fn+2 = 2Fn+2 + Fn+1 = 3Fn+1 + 2Fn ≤ 8Fn, а
Fn+5 = 3Fn+2 + 2Fn+1 = 5Fn+1 + 3Fn = 8Fn + 5Fn–1 ≥ 8Fn + 2,5Fn > 10Fn. (*)
а) Пусть Fn – наименьшее m-значное число Фибоначчи. Тогда Fn–1 < 10m–1 ≤ Fn. Значит, Fn+5 > 10Fn ≥ 10m, то есть m-значных чисел Фибоначчи не больше пяти. Но Fn+4 < 8Fn–1 < 10m, то есть m-значных чисел Фибоначчи не меньше четырёх.
б) Утверждение эквивалентно неравенству F5n+2 ≥ 10n, которое легко доказывается по индукции с использованием неравенства (*).
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 4 |
| Название | О том, как размножаются кролики |
| Тема | Классическая комбинаторика |
| задача | |
| Номер | 03.138 |
