As always, we should start with knowing the rules and/or definitions.
THE PRODUCT RULE: “Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.” Discrete Mathematics and its applications by Rosen.
In this case, we can apply a similar approach that we applied here.
If the bit strings must have length n, and start and end with 1, we can just calculate how many bit strings of length n-2 are there.
Let’s write the problem in the same way that the rules are defined.
We can choose the first bit in 2 ways. Then, for each of the 2 ways, we can choose the second bit in 2 more ways, and so on until we have chosen n-2 bits.
After stating the problem in this way, it becomes clear that we must apply the product rule.
So, we multiply 2 (the ways we can do each task) n-2 times (the number of tasks).
Answer:
There are 2n-2 bit strings of length n, where n is a positive integer and each bit string starts and ends with 1.
Related exercises:
- An office building contains 27 floors and has 37 offices on each floor. How many offices are in the building?
- How many bit strings of length ten both begin and end with a 1?
- How many different three-letter initials can people have?
- There are 18 mathematics majors and 325 computer science majors at a college