Prove that the number of n-digit binary numbers that have no consecutive 1’s is the Fibonacci number F(n+2).

Question

For example, for n = 2 there are three such numbers (00, 01, and 10), and 3 = F(2+2) = F4. Also, for n = 3 there are five such numbers (000, 001, 010, 100, 101), and 5 = F(3+2) = F5.

 

 

Mathematical induction proof is supposed to be used to answer this question

Answer 1

F3=2 and there are two 1-digit binaries: 0 and 1. So the base case holds.

If we call the number of n-digit binary numbers with no consecutive 1's B[n] then B1=2.

Assume B[n]=F[n+2], and let's find B[n+1]. F[n]=F[n-1]+F[n-2] by definition. F[n+2]=F[n+1]+F[n].

B[n]=F[n+1]+F[n]=B[n-1]+B[n-2] according to our assumption or hypothesis.

Let's look at the set of 3-digit binaries with no consecutive 1's: {000 001 010 100 101}.

Now move on to the set of 4-digit binaries by including this set by prefixing a 0 then a 1:

{0000 0001 0010 0100 0101 1000 1001 1010 1100 1101}. The set size has doubled but we have caused some consecutive 1's in the second half because of the leading 1. However, if we remove the last two elements we get {0000 0001 0010 0100 0101 1000 1001 1010}. The last 3 elements have 10 consistently as the first pair of digits. The other pair of digits happens to be the set of 2-digit binaries with no consecutive 1's.

Therefore the number of 4-digit binaries with no consecutive 1's is B3+B2, so B4=B3+B2. This is of course because we have to place a 0 between the leading 1 and the rest of the binary digits (bits) so that we don't place two 1's together.

If we go on to 5-digit binaries the same pattern emerges. 4-digit: {0000 ... 1010}⇒{00000 ... 01010 10000 10010 10100 10101}. B5=B4+B3. Note the second-half leading 10 followed by the 3-digit set with no consecutive 1's.

This is true for all natural numbers n. So B[n]=F[n+1]+F[n]=B[n-1]+B[n-2]. And B[n]=F[n+2].