Q on recurrence

[Sonal7]

This question is beautiful. I thought I would share this. I am getting through as I can see the pattern.

 

[Sonal7]

I got part a,
n=1 so the permutations which are allowed are 1 and 0, hence b₁=2
n=2 so the permutations which are allowed are 00,01,10, hence b₂=3
I can see that b_n=b_n-1+b_n-2

 

[pka]

n=1 so the permutations which are allowed are 1 and 0, hence b₁=2
n=2 so the permutations which are allowed are 00,01,10, hence b₂=3
I can see that b_n=b_n-1+b_n-2

You are asked to explain why \(b_n=b_{n-1}+b_{n-2}\)
Explain why we can take any string from \(b_{n-2}\) and to its end add \(01\) to get a string in \(b_{n}\).
Now take any string from \(b_{n-1}\) what can we add to get a string in \(b_{n}~?\).
Have we constructed all strings in \(b_{n}~?\).

 

[Sonal7]

I cant quite picture this yet, I will give it some time and use drawings.

 

[pka]

I cant quite picture this yet, I will give it some time and use drawings.

Here is some help by way of an example.
\(B_7\) is the set of all bit-strings of length seven which do not have two consecutive ones.
Ex. \(0101001\in B_7\) if we add \(\color{blue}01\) we get \(0101001{\color{blue}01}\in B_9\)
Taking any string from \(B_7\) and affixing \(\color{blue}01\) its right end gives a term in \(B_9\). THINK ABOUT IT.
Likewise, taking any string from \(B_8\) and affixing \(\color{blue}0\) its right end gives a term in \(B_9\). WHY?
Is it true that doing both operations we get ALL of \(\bf{B_9}~\)?
Have we shown that \(B_{n+1}=B_{n+2}+B_{n-1}~\)?

 

[pka]

Here is some help by way of an example.
\(B_7\) is the set of all bit-strings of length seven which do not have two consecutive ones.
Ex. \(0101001\in B_7\) if we add \(\color{blue}01\) we get \(0101001{\color{blue}01}\in B_9\)
Taking any string from \(B_7\) and affixing \(\color{blue}01\) its right end gives a term in \(B_9\). THINK ABOUT IT.
Likewise, taking any string from \(B_8\) and affixing \(\color{blue}0\) its right end gives a term in \(B_9\). WHY?
Is it true that doing both operations we get ALL of \(\bf{B_9}~\)?
Have we shown that \(B_{n+1}=B_{n+2}+B_{n-1}~\)?

There is a typo in the last line: \(B_{n}=B_{n-2}+B_{n-1}~\)