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

[Shadow]

Прочитайте в Википедию "Фибоначчиева система счисления". Там есть доказательство. И оно практически такое же.

[ewert]

Немножко пофилософствую. Конечно, суть дела в том, что последовательность Фибоначчи приблизительно соответствует некоторой геометрической прогрессии с достаточно немаленьким знаменателем. Однако произносить эти слова вслух, разумеется, крайне не рекомендуется.

-- Пт ноя 25, 2011 20:22:38 --

Shadow в сообщении #507953 писал(а):

Прочитайте в Википедию "Фибоначчиева система счисления". Там есть доказательство.

Прочитал. Там оно как-то неполноценно. Где ссылка на т.наз. "теорему Цекендорфа"?... (я такой даже и не знаю, естественно)

[Shadow]

Действительно нет ссылка на теорему. Но думаю и без нее ясно. Можно закодировать любое число нулями и единицами, причем две сосредние единицы невозможны.
$f_{n-1}<f_n\leqslant a<f_{n+1}$ У числа "a" в разряде n единичка. Осталось закодировать $a'=a-f_n$
Допустим, что $a' \geqslant f_{n-1}$ . Тогда $a'+f_n \geqslant f_{n-1} +f_n$
$a \geqslant f_{n+1}$. Противоречие. Т.е в разряде $n-1$ не может стоять единичка. Я так понял.

Правка: "В разряде n" и n-1 читать в 1-ом и 2-ом разряде

[svv]

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

Конечно, суть дела в том, что последовательность Фибоначчи приблизительно соответствует некоторой геометрической прогрессии с достаточно немаленьким знаменателем.

Вы имели в виду -- с достаточно маленьким? Он достаточно мал, чтобы появилась неоднозначность, и Whitaker сейчас пожинает её плоды.
$\varphi^{n+1}=\varphi^{n}+\varphi^{n-1}$

[ewert]

svv в сообщении #508006 писал(а):

Он достаточно мал, чтобы появилась неоднозначность,

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

[Shadow]

Действительно, там доказательство существования, но нет доказательство единствености. Ну, что делать. Придется без Цекендорфа обойтись.

[Whitaker]

А как доказывается единственность представления?

[ewert]

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

А как доказывается единственность представления?

Не знаю, как там у Цекендорфа, а тут -- автоматом. Последнее слагаемое просто обязано быть $f_{n+1}$, а все предыдущие -- единственны по индукции.

-- Пт ноя 25, 2011 22:58:51 --

Shadow в сообщении #508035 писал(а):

Действительно, там доказательство существования

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

[arseniiv]

(Оффтоп)

Whitaker, я видел в «Конкретной математике» простую, но весёлую задачку: доказать, что число $\sum_{n=0}^{\infty} b^{-n} F_n$ рационально ($b$ — рациональное. Довольно наглядный вид задача приобретает при $b = 10$). Может быть, вам она придётся по душе!

[svv]

(arseniiv)

"Конкретная математика для реальных пацанов"?

[arseniiv]

(2 svv.)

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

[Whitaker]

svv в сообщении #508139 писал(а):

(arseniiv)

"Конкретная математика для реальных пацанов"?

P.S. Благодарю Всех ИСН, ewert, svv за помощь и внимание к топику.
P.P.S. Оказывается в книжке Н. Н. Воробьева "Числа Фибоначчи" (4-ое издание) также приводится доказательство этого факта

-- Вс ноя 27, 2011 11:12:53 --

Если кто-нибудь читал эту книжку скажите пожалуйста что она из себя представляет?
Просто я с числами Фибоначчи мало знаком и хотелось бы на досуге познакомиться с ними поближе

[Sonic86]

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

Если кто-нибудь читал эту книжку скажите пожалуйста что она из себя представляет?

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

[Whitaker]

Спасибо за информацию Sonic86