(Теорема Цекендорфа) Любое натуральное число либо само является числом Фибоначчи, либо представляется единственным образом в виде суммы нескольких чисел Фибоначчи (кроме F1, его использовать нельзя), среди которых нет соседних. Например: 444 = 377 + 55 + 8 + 3 + 1 = $%{F_{14}} + {F_{10}} + {F_6} + {F_4} + {F_2}$%.

а) Докажите, что каждое натуральное число возможно представить таким образом.

б) Дана некоторая сумма чисел Фибоначчи, среди которых нет соседних и самое большое число $%{F_n}$%. Докажите, что эта сумма меньше $%{F_{n + 1}}$%.

в) Докажите, что представление каждого числа в виде указанной суммы единственно.

задан 6 Май '19 19:54

1

https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A6%D0%B5%D0%BA%D0%B5%D0%BD%D0%B4%D0%BE%D1%80%D1%84%D0%B0

Весьма вероятно, что это утверждение было известно до рождения Цекендорфа.

(6 Май '19 20:19) EdwardTurJ

Спасибо, но остался вопрос о доказательстве леммы по индукции, в статье Википедии нет доказательства о том, что сумма элементов строго меньше следующего числа Фибоначчи, т.е. пункт б) данной задачи.

(7 Май '19 15:00) Igore

@Igore: пункт б) доказывает индукцией по n. Если нет соседних, и самое большое число F(n), то среди оставшихся слагаемых нет F(n-1). Значит, самое большое слагаемое (если оно есть) не превосходит F(n-2). По предположению, сумма слагаемых без учёта F(n) меньше F(n-1). Тогда с учётом F(n) вся сумма меньше F(n-1)+F(n)=F(n+1).

Такого рода промежуточные пункты обычно даются не для усложнения задач (дабы что-то дополнительное доказать), а для упрощения -- с идеей, что они получаются автоматически.

(7 Май '19 18:35) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×37

задан
6 Май '19 19:54

показан
157 раз

обновлен
7 Май '19 18:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru