Последовательность Фибоначчи

[Whitaker]

Здравствуйте уважаемые!
Наткнулся на такую задачку, но как решить ее я пока не знаю. Подскажите пожалуйста с чего начать.
Пусть $\{f_n\}$-последовательность Фибоначчи: $f_0=f_1=1$ и $f_{n+1}=f_{n}+f_{n-1}$ при $n \in \mathbb N$. Тогда любое натуральное число $N$ можно единственным образом представить в виде

$$N=\sum \limits_{k=0}^{\infty}\alpha_k f_k,$$

где $\alpha_k \alpha_{k+1}$=0 для любого $k \geq 0$

С уважением, Whitaker.

[ИСН]

Первые несколько руками, дальше по индукции. Но у Вас условие сформулировано как-то вычурно. Вы его понимаете?

-- Пт, 2011-11-25, 17:14 --

(И не совсем правильно к тому же.)

[Whitaker]

ИСН да я условие вроде понял.
Его можно сформулировать так: Доказать, что любое натуральное число $N$ можно представить в виде суммы чисел Фибоначчи, причем каждое число будет входить в сумму не более одного раза и никакие два соседних числа не войдут вместе.

-- Пт ноя 25, 2011 16:18:28 --

Т.е. $\alpha_k=0$ или $\alpha_k=1$

-- Пт ноя 25, 2011 16:20:14 --

Запись $\alpha_k \alpha_{k+1}=0$ означает, что двух подряд единиц быть не может

[ИСН]

Ага, так значительно лучше. (В первоначальном тексте ниоткуда не следовало, что $\alpha_k$ не может быть равно 2 или чему угодно ещё).

[Whitaker]

Да вы правы ИСН.
Из первого текста не всё сразу ясно.

[ИСН]

Ну а тогда - как я сказал, индукция. Предположим, мы добрались до 8 и там всё получается. Тогда можем ли мы добраться до 13?

[Whitaker]

База индукции: пусть $N=1$, тогда:
$1=0\cdot f_0+1\cdot f_1+0\cdot f_2+0\cdot f_3+.....$
$1=1\cdot f_0+0\cdot f_1+0\cdot f_2+0\cdot f_3+.....$
Пусть утверждение справедливо при $N$.
Вот как доказать, что она верна при $N+1$ не получается.
Чем воспользоваться?

[ewert]

По индукции $\sum\limits_{k=1}^{n-1}f_k<f_{n+1}.$ Из этого сразу следует, что любое число из промежутка $\big[f_{n+1};f_{n+2}\big)$ должно содержать в своём разложении число $f_{n+1}$ (и, разумеется, не может содержать $f_n$), а по индукционному предположению дополнение этого числа до $f_{n+1}$ раскладывается по предыдущим единственным образом.

-- Пт ноя 25, 2011 17:46:13 --

Только надо, конечно, какую-то оговорку насчёт единичек сделать. Или выкинуть одну из них из последовательности, или сделать оговорку насчёт единственности.

[Whitaker]

ewert в сообщении #507855 писал(а):

По индукции $\sum\limits_{k=1}^{n-1}f_k<f_{n+1}.$ Из этого сразу следует, что любое число из промежутка $\big[f_{n+1};f_{n+2}\big)$ должно содержать в своём разложении число $f_{n+1}$ (и, разумеется, не может содержать $f_n$), а по индукционному предположению дополнение этого числа до $f_{n+1}$ раскладывается по предыдущим единственным образом.

-- Пт ноя 25, 2011 17:46:13 --

Только надо, конечно, какую-то оговорку насчёт единичек сделать. Или выкинуть одну из них из последовательности, или сделать оговорку насчёт единственности.

ewert можеть быть у Вас суммированние от нуля?

[ewert]

С начала, естественно. А на способ нумерации я просто не обращал внимания -- это всё равно условность.

[Whitaker]

ewert я последовал Вашим подсказкам:
1) Покажем, что $f_1+f_2+...+f_{n-1}<f_{n+1}$ (не по индукции)
Так как $f_1+f_2+...+f_{n-1}=f_{n+1}-1$ и $f_{n+1}-1<f_{n+1}$, то $f_1+f_2+...+f_{n-1}<f_{n+1}$
2) Возьмём любое натуральное число $N \in \big[f_{n+1};f_{n+2}\big)$.
Так как $f_{n+1} \leq N < f_{n+2}$, то $0 \leq N-f_{n+1} < f_{n+2}-f_{n+1}$, т.е. $0 \leq N-f_{n+1} < f_n$. Из последнего видно, что число $N$ должно содержать в своем разложении $f_{n+1}$, но $f_n$ он будет содержать. Тогда $N=f_{n+1}+N_1,$ где $N_1<f_{n}$.
Дальше мне пока неясно.

[ewert]

Пардон, я уж и сам сообразил, что чего-то там не то ляпнул. Там нужно немножко более изысканное утверждение: что любая разрешённая сумма до $f_n$ включительно меньше, чем $f_{n+1}$. Вот тогда-то уж и впрямь ясно, что любое число из $\big[f_{n+1};f_{n+2})\big$ обязано иметь в своём разложении $f_{n+1}$ и т.д.

Ну это тоже легко доказывается по индукции. Если та сумма не содержит $f_n$, т.е. если это фактически разрешённая сумма до $f_{n-1}$ включительно, то она по индукционному предположению меньше $f_n$ и уж тем более меньше $f_{n+1}$. Если же она $f_n$ содержит, то не может содержать $f_{n-1}$. Но тогда все предыдущие слагаемые, образующие некую разрешённую сумму до $f_{n-2}$ включительно, опять же по индукционному предположению меньше, чем $f_{n-1}$. Так что вся сумма в целом меньше, чем $f_{n-1}+f_n=f_{n+1}$, ч.т.д.

[Whitaker]

ewert извиняюсь, а что значит разрешённая сумма?

[ewert]

Whitaker в сообщении #507936 писал(а):

ewert извиняюсь, а что значит разрешённая сумма?

Ну, очевидно, сумма, в которой (согласно условиям задачки) никакие два соседних числа Фибоначчи одновременно не присутствуют. А что бы это ещё могло быть?...

[Whitaker]

Аааа да. Извиняюсь за глупый вопрос ewert.