For n N let Bn be the set of all ndigit binary numbers For e

For n N, let Bn be the set of all n-digit binary numbers. For example B3 = {000, 001, 010, 100, 011, 101, 110, 111}.

(a) Show that |Bn| = 2^n.

(b) Prove that the number of n-digit binary numbers that have no consecutive 1’s is the Fibonacci number Fn+2. For example, for n = 2 there are three such numbers (00, 01, and 10), and 3 = F2+2 = F4. Also, for n = 3 there are five such numbers (000, 001, 010, 100, 101), and 5 = F3+2 = F5.

(c) Use parts (a) and (b) to show Fn+2 <= 2^n where Fn means the nth Fibonacci number.

Solution

a) Bn is a set of all n-digit binary numbers

each digit can be either 0 or 1 2 possibilities

there are n-digits and 2 posibilities for each digit so

Bn will have 2^n binary numbers

b)

Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1.

We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:

to prove by induction

B1={0,1} 2 =F3

true for n=1

let us assume it works for n and n-1 and is a fibonacci number

a[n]=a[n-1]+b[n-1]

b[n]=b[n-1]

|Bn-1|=a[n-1]+b[n-1] =Fn+1

|Bn|=a[n]+b[n] =Fn+2

|Bn+1|=a[n+1]+b[n+1]

a[n+1] =a[n]+b[n]

b[n+1]=a[n]

|Bn+1|=a[n]+b[n]+a[n]=Fn+2+a[n-1]+b[n-1]=(Fn+2)+(Fn+1)=(Fn+3)

true for n=1 and assumed it is true for n-1 and n

hence proved it is true for n+1 by induction

c)We haved proved from a that we will have 2^n binary numbers in Bn

and number of binary numbers with no consecutive ones in Bn will be Fn+2

So from these two we can know that Fn+2 will be at max 2^n as we will have maximum of 2^n numbers in Bn