Find a recurrence relation and initial conditions for the sequence {a_n} if a_n

Question

Find a recurrence relation and initial conditions for the sequence {a_n} if a_n is the number of bit strings of length n that do not contain three consecutive 0's Find a recurrence relation and initial conditions for the sequence {a_n} if a_n is the number of bit strings of length n that contain three consecutive 0's Find a recurrence relation and initial conditions for the number of sequences over the alphabet {a, b, c} that do not contain two consecutive a's. Find a recurrence relation and initial conditions for the number of sequences over the alphabet {a, b, c} that contain two consecutive a's. A child takes either big steps or little steps. The big steps cover 20 inches. and the little steps cover 10 inches. Let a_n be the number of ways there are for the child to walk 10n inches. (a) Write down a recurrence relation and initial conditions for {a_n} (b) Determine the number of ways for the child to walk 10 feet. Find an explicit formula for the number of partitions of the positive integer k into parts no larger than 2. Let q(n) be the number of partitions of a set with n elements into sets with at most four elements each. (a) Write down a recurrence relation for q, and give the conditions. (b) Compute q (6)

Explanation / Answer

It appears we are looking at partitions of 'k' of size one and two. There is one partition of k of size 1, namely 'k' itself. Suppose k is even that is k = 2p for some p

then the partitions of size two are 1+(k-1), 2+(k-2), ....,(p-1)+(p+1), p+p. Thus there are in total p+1 partitions of size 2 or 1, if k = 2p for some p.

Now suppose k is odd and that k = 2p+1 for some p.
Then partitions of size 2 are 1+ (k-1), 2+(k-2) , p+(p+1). Thus there are in total p+1 partitions of k = 2p+1 of size 2 or less.

Combining the two we see that the number of such partitions of k is [(k+1)/2] where [x] denotes the greatest integer function.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.