Question

induction Consider the set of bitstrings x ∈ {0, 1} n+k with n zeros and k ones with the additional condition that no ones are adjacent. (For n = 3 and k = 2, for example, the legal bitstrings are 00101, 01001, 01010, 10001, 10010, and 10100.) Prove by induction on n that the number of such bitstrings is n+1 k ? .

Answer 1

The answer is 6.

Explanation:

From the question given,

Let us consider the set of bit strings x ∈ { 0.1} with n zeros and k ones.

The additional condition that no one are adjacent for n=3 and k=2

Then

(n+1 k) = (n+1)ǃ/k ǃ (n+1 )ǃ = 4ǃ/2ǃ (2ǃ)

which is

n+1 k) = (n+1)ǃ/k ǃ (n+1 )ǃ = 4ǃ/2ǃ (2ǃ) = 24ǃ/ 2*2 =24/4

Therefore

24ǃ/ 2*2 =24/4 = 6