набор не содержащего пары соседних чисел Фибоначчи

freeway78

любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно. :o

freeway78

Да но там нет единственности

freeway78

Спасибо английский только конечно придется погуглить.

freeway78

А другого метода нет? каких нибудь производящих функций

freeway78

Объясните плиииз

kachokslava

ну типа если содержит пару соседних, то заменяем на их сумму - получаем новое число фибоначчи, профит!

incwizitor

Объясните плиииз
из английской версии:
доказательство состоит из двух частей
1) существование подобного представления для любого натурального числа
2) единственность такого представления
1) существование на русском описано здесь http://ru.wikipedia.org/wiki/%D4%E8%E1%EE%ED%E0%F7%F7%E8%E5%...
2) единственность опирается на лемму о том, что сумма последовательности разных чисел Фибоначчи без соседей, в которых максимальным является [math]$$F_j$$[/math], строго меньше [math]$$F_{j+1}$$[/math]
док-во леммы:
по индукции по номеру числа Фибоначчи [math]$$j$$[/math] :
основание индукции: для суммы, у которой максимальным числом Фибоначчи является 1 это очевидно (след. число Фибоначчи равно 2 j = 1
шаг индукции: доказали для всех S, у которых максимальным числом Фибоначчи является [math]$$F_j$$[/math]
Рассмотрим последовательность чисел Фибоначчи (без соседей) с максимальным числом [math]$$F_{j+1}$$[/math]
Так как соседей нет, то след. по величине слагаемое не больше [math]$$F_{j-1}$$[/math], то есть сумма всех слагаемых, кроме [math]$$F_{j+1}$$[/math], строго меньше [math]$$F_j$$[/math]. Следовательно, вся сумма строго меньше, чем [math]$$F_j + F_{j+1} = F_{j+2}$$[/math].
Лемма доказана.
Применим эту лемму:
Пусть есть две разные последовательности S и T чисел Фибоначчи, которые в сумме дают одно и то же число. Будем считать, что общих членов нет (их можно легко удалить, суммы при этом останутся быть равными). S >0, T>0
Пусть максимальные числа в этих последовательностях равны соотвественно [math]$$F_s$$[/math] и [math]$$F_t$$[/math]. Без ограничения общности можно считать, что [math]$$F_s < F_t$$[/math] (строго меньше, так как дубликаты удалили).
Согласно лемме сумма любой последовательности (в том числе и S) с максимальным членом [math]$$F_s$$[/math] строго меньше следующего числа Фибоначчи: [math]$$S < F_{s+1} <= F_t <= T \Rightarrow S \not = T$$[/math].
Получили противоречие, значит, таких разных последовательностей S и T не существует.

freeway78

спасибо!

freeway78

Большое спасибо!
Оставить комментарий
Имя или ник:
Комментарий: