Доказательство пользовательских двоичных строк

Фибоначчи определяется рекурсивно для этого вопроса как: F~0 = 1 F~1 = 1 F~n = F~n-1 + F~n-2 для n >= 2 Таким образом, пользовательская двоичная строка всегда начинается с 1 и никогда имеет два последовательных. Если s = s~Ls~L-1...s~1 является такой строкой длины L, где s~i находится в {0,1}, число, представленное s, равно: n(s) = Sigma (i = от 1 до L) s~ix F~i Пример: n(1000101) = F~7 + F~3 + F~1 = 21 + 3 + 1 = 25

(a) Докажите для каждого L >= 1, если s — произвольное двоичное число длины L, n(s) >= F~L

(b) Докажите для каждого L >= 1, если s — произвольное двоичное число длины L, n(s) ‹ F~L + 1

Я пытался доказать с помощью индукции, но безуспешно, скорее всего, потому, что я делаю это неправильно. Я не знаю, как еще доказать это для общего случая L > 1.

'~' означает, что у переменной есть индекс


string binary proof
person kindofastudent    schedule 25.09.2014    source источник
comment
Вы уверены, что правильно сформулировали вопрос? Мне кажется, что оба эти утверждения ложны. Для части a рассмотрим строку 10 с L=2. Согласно вашей формуле, n(10) = 1 меньше, чем F~2 = 2. Для части b рассмотрим 101 длиной 3. n(101) = 1xF~1 + 1xF~3 = 1 + 3 = 4, что в точности равно F~L + 1   -  person Jason Baker    schedule 25.09.2014
comment
Забыл добавить пример: n(1000101) = F~7 + F~3 + F~1 = 21 + 3 + 1 = 25, поэтому для n(10) = 2, потому что n(s) = s2 x f2 + s1 x f1 = 2   -  person kindofastudent    schedule 25.09.2014
comment
Да, вы правы насчет n(10). Хорошо, тогда часть а верна, и это легко доказать (индукция не требуется). Однако я все еще не уверен, что часть b верна для всех L. Допустил ли я какие-либо ошибки при расчете n(101) или при интерпретации полученного ответа?   -  person Jason Baker    schedule 25.09.2014
comment
Вы не знали, но F ~ L + 1 больше, поскольку L, о котором мы говорим, — это длина s. Таким образом, длина s = 3 и n(101) = 4, но F~L+1 = F~4 = 5   -  person kindofastudent    schedule 25.09.2014
comment
О, хорошо, я неправильно понял; Я думал, что верхняя граница равна (F~L)+1, но вы имели в виду F~(L+1). Теперь мы на одной странице   -  person Jason Baker    schedule 25.09.2014
comment
о да, извините, нужно было уточнить, но когда вы говорите, что легко доказать без индукции, вы имеете в виду случаи или?   -  person kindofastudent    schedule 25.09.2014
comment
Я собираюсь начать писать ответ, который должен прояснить   -  person Jason Baker    schedule 25.09.2014

Ответы (1)


arrow_upward
0
arrow_downward

Начнем с А.

Я бы доказал это так:

Пусть s будет пользовательской двоичной строкой с L=k, такой что k>=1. По определению пользовательских двоичных строк у нас должно быть s~k = 1 Следовательно, n(s) = F~k + n(s~(k-1)...s(1)) = F~L + n(s~(k-1) ... s(1)), или число, представленное s, равно F~L плюс число, представленное оставшимися k-1 цифрами s. Поскольку у нас не может быть строки с отрицательной длиной, мы должны иметь это n(s) >= F~L

Однако, если вам нужно доказать это индуктивно, вы можете сделать это следующим образом:

Базовый вариант: пусть L=1 и s будут пользовательской двоичной строкой длины 1. У нас должно быть s=1 по определению. Поэтому n(s) = n(1) = 1xF~1 = F~L, как и требовалось.

Индуктивная гипотеза. Предположим, что n(s) >= F~L вместо L=1,2,...k-1.

Индуктивный случай: пусть L=k, а s – пользовательская двоичная строка длиной k.

Если s содержит только одну цифру, равную 1, это эквивалентно базовому случаю, и мы закончили.

Если s содержит более одной цифры, равной 1, пусть i будет индексом второго вхождения, а t будет пользовательской двоичной строкой, представленной цифрами s~i ... s~1. Тогда у нас есть это n(s) = 1xF~k + n(t) = F~L + n(t). Поскольку t имеет длину k-i, по предположению индукции мы имеем n(s) >= F~L + F~(k-i)>= F~L, что и требовалось.

Хорошо, B будет сложнее. Я собираюсь доказать это индуктивно, потому что я думаю, что это проще.

Базовый вариант: пусть L=1 и s будут пользовательской двоичной строкой длины 1. У нас должно быть s=1 по определению. Поэтому n(s) = n(1) = 1xF~1 = 1 < 2 = F~2.

Индуктивная гипотеза. Предположим, что n(s) ‹ F~(L+1)forL=1,2,...,k-1`.

Индуктивный случай. Пусть L=k и s будут пользовательской двоичной строкой длины k.

Если s имеет только одну цифру, равную 1, это эквивалентно базовому случаю, и мы закончили. Если s содержит более одной цифры, равной 1, пусть i будет индексом второго вхождения, а t будет пользовательской двоичной строкой, представленной цифрами s~i ... 1.

Очевидно, что n(s) = F~L + n(t). По индуктивному предположению мы знаем, что n(t) < F~(i+1). Поскольку в пользовательских двоичных строках не может быть последовательных цифр 1, у нас также есть i <= L-2 или i+1 <= L-1, что означает, что F~(i+1) <= F~(L-1), поскольку последовательность Фибоначчи строго возрастает.

Собираем все вместе: n(s) = F~L + n(t) < F~L + F~(i+1) < F~L + F~(L-1) = F~(L+1).

Поэтому n(s) < F~(L+1), как и требовалось.

person Jason Baker    schedule 25.09.2014