6. A string that contains only 0s 1s and 2s is called a ternary string
a) find a recurrence relation for the number of ternary strings that contain two consecutive 0s
b) what are the initial conditions
c) how many ternary strings of length six contain two consecutive 0s

The next 3 problems deal with a variation of the Josephus problem described by Graham, Knuth, and Patashnik in [GrKnPa94].? This problem is based on an account by the historian Flauvius Josephus, who was part of a band of 41 Jewish rebels trapped in a cave by the Romans during the Jewish-Roman war of the first century.? The rebels pre-ferred suicide to capture; they decided to form a circle and to repeatedly count off around the circle, killing every 3rd rebel left.? However, josephus and another rebel did not want to be killed this way; they determined the positions where they should stand to be the last two rebels remaining alive.? The variation we consider begins with n people, numbered 1 to n, standing around a circle.? In each stage, every second person still left alive is eliminated until only one survives.? We denote the number of the survivor by J(n).

7) Determine the value of J(n) for each integer n with 1 <= n <= 16.? Use these values to conjecture a formula for J(n).? Hint: Write n=2^m +k, where m is a nonnegative integer and k is a nonnegative integer less than 2^m.

8) Show that J(n) satisfies the recurrence relation J(2n) = 2J(n) - 1 and J(2n+1) = 2J(n) + 1, for n >= 1, and J(1) = 1.

9) Use mathematical induction to prove that the formula you conjectured in exercise 50, making use of the recurrence relation from the previous exercise.

10) a. Assume that in the average case, the running time for Quicksort is f(n) = 2f(n/2)+ n. Use the Master Theorem to estimate its closed-form running time.

b. Do the same for Slowsort, whose running time is f(n) = 4f(n/2)+n.

6).a) Let t(n) denote the number of ternary string with length n containing two consecutive 0s. For a ternary string a1a2...an, if a1=0, then the number of such string is 3^(n-1). and the number of the strings satisfying a1=0 and a2= is 2*3^(n-2). We can ...

Let A = { 1, 2, 3, 4 } , and let R be the relation defined on A defined by:
R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (3,4), (1,3), (2,4)}
(a) Draw the digraph of this relation.
(b) Which of the properties: reflexive, antisymmetric and transitive are true for the given relation? Begin your discussion by defining each

See the attached file.
1. How many bit strings of length ten contain either at least five consecutive 0's or at least five consecutive 1's? explain
2. Which is more likely: rolling a total of 8 when two dice are rolled, or rolling a total of 8 when three dice are rolled? explain
3. Three fair dice are rolled.Let X be th

Looking for some answers to discrete math questions. Must show work so that I can understand how you achieved the results.
See attached.
1. Note the contrapositive of the definition of one-to-one function given on of the text is: If a ≠ b then f(a) ≠ f(b). As we know, the contrapositive is equivalent to (another way o

.Derive the statement as corollaries of other theorems from the text or of statement you have proved true in the exercise.
Prove that if one solution to a quadratic equation of the form x^2+bx+c=0 is rational (where b and c are rational), then the other solutions is also rational. (Use the fact that if the solutions of the e

What is a probability distribution and its purpose?
Distinguish between discrete and continuous probability distributions. Give an example of each.
What is randomness? Assume you have an Excel worksheet of the dimension, A1:E101. The first row contains data labels. How would you randomize the data file and to select a

Suppose that X is a discrete random variable with P(X=1) = θ and P(X=2)= 1- θ. Three independent observations of X are made: X1 = 1, X2 = 2, X3 = 2.
Find the Method of Moments estimate of θ. Please show your work.

Q1) Use the standard logical equivalences to simplify the expression
(ㄱp ^ q) v ㄱ(pVq)
Q2) consider the following theorem
"The square of every odd natural number is again an odd number"
What is the hypothesis of the theorem? what is the conclusion? give a direct proof of the theorem.
Q3) consider the follo