Search code examples
stringbinaryproof

Proof of custom binary strings

Fibonacci is defined recursively for this question as: F~0 = 1 F~1 = 1 F~n = F~n-1 + F~n-2 for n >= 2 So a custom binary string always begins with 1 and never has two consecutive ones. If s = s~Ls~L-1...s~1 is such a string of length L where s~i is in {0,1}, the number represented by s is: n(s) = Sigma (i = 1 to L) s~i x F~i Example: n(1000101) = F~7 + F~3 + F~1 = 21 + 3 + 1 = 25

(a) Prove for every L >= 1, if s is a custom binary number of length L, n(s) >= F~L

(b) Prove for every L >= 1, if s is a custom binary number of length L, n(s) < F~L + 1

I've tried to prove with induction with no luck most likely because I'm doing it wrong. I'm not sure how else to prove it for the general case of L > 1.

The '~' is to represent there is a subscript for the variable

Solution

  • Let's start with A.

    I would prove it this way:

    Let s be a custom binary string with L=k such that k>=1. By definition of custom binary strings, we must have s~k = 1 Therefore n(s) = F~k + n(s~(k-1)...s(1)) = F~L + n(s~(k-1) ... s(1)), or the number represented by s is equal to F~L plus the number represented by the remaining k-1 digits of s. Since we cannot have a string with negative length, we must have that n(s) >= F~L

    However, if you need to prove it inductively, you could do it this way:

    Base case: Let L=1 and s be a custom binary string of length 1. We must have s=1, by definition. Therefore n(s) = n(1) = 1xF~1 = F~L, as required.

    Inductive Hypothesis: Assume that n(s) >= F~L for L=1,2,...k-1.

    Inductive case: Let L=k, and let s be a custom binary string of length k.

    If s contains only one digit equal to 1, this is equivalent to the base case and we are done.

    If s contains more than one digit equal to 1, let i be the index of the second occurrence, and let t be the custom binary string represented by the digits s~i ... s~1. Then we have that n(s) = 1xF~k + n(t) = F~L + n(t). Since t has length k-i, by the inductive hypothesis we have n(s) >= F~L + F~(k-i)>= F~L, as required.

    Okay, B is going to be harder. I'm going to prove it inductively, because I think it's easier.

    Base case: Let L=1 an s be a custom binary string of length 1. We must have s=1, by definition. Therefore n(s) = n(1) = 1xF~1 = 1 < 2 = F~2.

    Inductive Hypothesis: Assume that n(s) < F~(L+1)forL=1,2,...,k-1`.

    Inductive Case: Let L=k and s be a custom binary string of length k.

    If s has only one digit equal to 1, this is equivalent to the base case and we're done. If s has more than one digit equal to 1, then let i be the index of the second occurrence, and t be the custom binary string represented by the digits s~i ... 1.

    It is obvious that n(s) = F~L + n(t). By the inductive hypothesis we know that n(t) < F~(i+1). Since custom binary strings cannot have consecutive digits be 1, we also have that i <= L-2, or i+1 <= L-1, which means that F~(i+1) <= F~(L-1) since the Fibonacci sequence is strictly increasing.

    Putting it all together: n(s) = F~L + n(t) < F~L + F~(i+1) < F~L + F~(L-1) = F~(L+1).

    Therefore n(s) < F~(L+1), as required.