Question

Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.) Let Zn be the number of binary stri

Bivariate numerical data
ANSWERED
asked 2021-03-07
Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.)
Let Zn be the number of binary strings of length n that do not contain the substring 000
Find a recurrence relation for Zn
You are not required to find a closed form for this recurrence.

Answers (1)

2021-03-08

Consider such a sequence of n digits.
If the first digit is 1, then we must not have a substring 000 in the remaning part of this sequence. Thus, we have Zn-1 such sequences.
If the first digit is 0, then we look at the second digit. If the second digit is 1, then this sequence starts with 01, meaning that we must not have a substring 000 in the remaning n—2 digits. Therefore, there are Zn-2 such sequences.
If the second digit is 0, then this sequence starts with 00. This means that the third digit must be 1 (otherwise, we would have 000 in this sequence). Therefore, this sequence starts with 001, meaning that we must not have 00 asa substring in the remaining n —3 digits. Thus, there are Zn-3 such sequences.
This covers all cases. Therefore, the recurrence relation is \(Zn=Zn-1+Zn-2+Zn-3\)

0
 
Best answer

expert advice

Need a better answer?

Relevant Questions

asked 2021-01-31

(a) Find a closed-form solution for this recurrence relation: \(an=2\cdot an−1−n+1\) with \(a1=2a\)
(b) Prove that your closed-form solution is correct.

asked 2021-05-05
If John, Trey, and Miles want to know how’ | many two-letter secret codes there are that don't have a repeated letter. For example, they want to : count BA and AB, but they don't want to count“ doubles such as ZZ or XX. Jobn says there are 26 + 25 because you don’t want to use the same letter twice; that’s why the second number is 25.
‘Trey says he thinks it should be times, not plus: 26-25, Miles says the number is 26-26 ~ 26 because you need to take away the double letters. Discuss the boys’ ideas, Which answers are correct, which are not, and why? Explain your answers clearly and thoroughly, drawing ‘on this section’s definition of multiptication.. -
asked 2021-05-16
Consider the curves in the first quadrant that have equationsy=Aexp(7x), where A is a positive constant. Different valuesof A give different curves. The curves form a family,F. Let P=(6,6). Let C be the number of the family Fthat goes through P.
A. Let y=f(x) be the equation of C. Find f(x).
B. Find the slope at P of the tangent to C.
C. A curve D is a perpendicular to C at P. What is the slope of thetangent to D at the point P?
D. Give a formula g(y) for the slope at (x,y) of the member of Fthat goes through (x,y). The formula should not involve A orx.
E. A curve which at each of its points is perpendicular to themember of the family F that goes through that point is called anorthogonal trajectory of F. Each orthogonal trajectory to Fsatisfies the differential equation dy/dx = -1/g(y), where g(y) isthe answer to part D.
Find a function of h(y) such that x=h(y) is the equation of theorthogonal trajectory to F that passes through the point P.
asked 2021-05-09
The dominant form of drag experienced by vehicles (bikes, cars,planes, etc.) at operating speeds is called form drag. Itincreases quadratically with velocity (essentially because theamount of air you run into increase with v and so does the amount of force you must exert on each small volume of air). Thus
\(\displaystyle{F}_{{{d}{r}{u}{g}}}={C}_{{d}}{A}{v}^{{2}}\)
where A is the cross-sectional area of the vehicle and \(\displaystyle{C}_{{d}}\) is called the coefficient of drag.
Part A:
Consider a vehicle moving with constant velocity \(\displaystyle\vec{{{v}}}\). Find the power dissipated by form drag.
Express your answer in terms of \(\displaystyle{C}_{{d}},{A},\) and speed v.
Part B:
A certain car has an engine that provides a maximum power \(\displaystyle{P}_{{0}}\). Suppose that the maximum speed of thee car, \(\displaystyle{v}_{{0}}\), is limited by a drag force proportional to the square of the speed (as in the previous part). The car engine is now modified, so that the new power \(\displaystyle{P}_{{1}}\) is 10 percent greater than the original power (\(\displaystyle{P}_{{1}}={110}\%{P}_{{0}}\)).
Assume the following:
The top speed is limited by air drag.
The magnitude of the force of air drag at these speeds is proportional to the square of the speed.
By what percentage, \(\displaystyle{\frac{{{v}_{{1}}-{v}_{{0}}}}{{{v}_{{0}}}}}\), is the top speed of the car increased?
Express the percent increase in top speed numerically to two significant figures.
...