sh3lsh
  • sh3lsh
Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. I'm lost on how to start this.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
ganeshie8
  • ganeshie8
The number of \(n\) bit binary strings can be thought of as two sets : 1) Strings that end in \(1\) 2) Strings that end in \(0\)
ganeshie8
  • ganeshie8
Let \(a_n\) denote the number of \(n\) bit strings that do not have two consecutive 0's
ganeshie8
  • ganeshie8
If the string ends in \(1\), then the \(n-1\)th bit could be either \(0\) or \(1\) so the number of \(n\) bit strings that end in \(1\) and do not have two consecutive \(0\)'s are \(a_{n-1}\) |dw:1434309606750:dw|

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

ganeshie8
  • ganeshie8
If the string ends in \(0\), then the \(n-1\)th bit must be\(1\), consequently the number of \(n\) bit strings that end in \(10\) and do not have two consecutive \(0\)'s are \(a_{n-2}\) |dw:1434309743465:dw|
ganeshie8
  • ganeshie8
So the desired recurrence relation is \[\large a_{n}~~=~~a_{n-1}+a_{n-2}\]
ganeshie8
  • ganeshie8
see if you can work the initial conditions
sh3lsh
  • sh3lsh
\[a_{1} = 2 \\ 0 \: and \: 1 \\ a_{2} = 3 \\ 11, 01, 10 \\ correct? \]
ganeshie8
  • ganeshie8
Looks good!
sh3lsh
  • sh3lsh
You're great! Thanks! Can I ask you a quick question though? Often when I look at recurrence relationship answers, they have a(n) being something along of the lines of 2^ a(n-3). Would you have any idea why one would such a thing?
sh3lsh
  • sh3lsh
http://mathfaculty.fullerton.edu/sannin/teaching/471-fall14/GroupWork07-solns.pdf
ganeshie8
  • ganeshie8
\(2^n\) comes very naturally wgen working with binary strings because the total number of strings of length \(n\) is \(2^n\)
ganeshie8
  • ganeshie8
Let me ask you a question. In light of the original problem, can you work a recurrence relation for the number of bit strings of length n that CONTAIN two consecutive 0s. ?
sh3lsh
  • sh3lsh
Let me attempt
sh3lsh
  • sh3lsh
In this case, would I separate the cases into where it ends with a 1, 10, and 00?
ganeshie8
  • ganeshie8
use the original problem
sh3lsh
  • sh3lsh
Oh, so still ending with a 1 and ending with a 0?
ganeshie8
  • ganeshie8
Let \(a_n\) represents number of bit strings of length \(n\) that DO NOT have two consecutive 0's Let \(b_n\) represents number of bit strings of length \(n\) that CONTAIN two consecutive 0's
ganeshie8
  • ganeshie8
since total bit strings of length \(n\) is \(2^n\), do we have \[a_n+b_n = 2^n\] ?
sh3lsh
  • sh3lsh
Is that a question? I think that's true.
ganeshie8
  • ganeshie8
Yes, that means \(a_n = 2^n-b_n\) plug that in earlier recurrence relation
sh3lsh
  • sh3lsh
Why would you do that? We already have \[a_{n}\] Could we just do \[b_{n} = 2^{k}-(a_{n-1} + a_{n-2})\]
ganeshie8
  • ganeshie8
we can do that, but that is not a proper recurrence relation
ganeshie8
  • ganeshie8
we want to have a single sequence in a recurrence relation (all b_n s)
ganeshie8
  • ganeshie8
don't want a_n s
ganeshie8
  • ganeshie8
replace \(a_{n-1}\) and \(a_{n-2}\) also
sh3lsh
  • sh3lsh
How?
sh3lsh
  • sh3lsh
Unfortunately, I must leave. Thanks for helping me through this much!
ganeshie8
  • ganeshie8
\(a_{n-1}~~=~~2^{n-1}-b_{n-1}\)

Looking for something else?

Not the answer you are looking for? Search for more explanations.