Really struggling in this worksheet for discrete structures, can someone show me

Question

Really struggling in this worksheet for discrete structures, can someone show me the proper way? 1. A toll booth accepts only nickels, dimes, and quarters a. Find a recurrence relation for the number of ways to deposit n cents in the toll booth, where the order in which the coins are deposited matters. b. What are the initial conditions? 0. 2. A string that contains only 0s, 1s, and 2s is called a tenary string (12) a. Find a recurrence relation for the number of tenary strings of length n that contain two consecutive 1s b. What are the initial conditions? 128 01 60 X2 c. How many tenary strings of length six that contain two consecutive 1s? 49 144 41 8 3 ? 3. Suppose fin)-3Rn4) + 2 when n is divisible by 2, and f(1). 1. a. Find f(64). b. Find (256). 2 x 3 3(n) +2 SI IS llo 1 112

Explanation / Answer

1.a) A toll booth accepts 3 things only

an=2(an-1)+an-3

b)Initial conditions a0=1,a1=2,a2=4

take n=3 ->an=2(an-1)+an-3

a3=2(a3-1)+a3-3=2(a2)+a0=2(4)+1=9

2 a) an =an-1 +1

Tenary string of length n that contains two consecutive 1s

suppose length n=1 we have 1

length n=2 ->(11)

length n=3 we have 5 touples ->(011,110,112,211,111)

b)Initial conditions a0=1, a1=1

c)an= an-1+1

a2=a2-1+1=a1+1=1+1=2

a3=a3-1+1=a2+1=2+1=3

a4=a4-1+1=a3+1=3+1=4

a5=a4+1=4+1=5

a6=a5+1=5+!=6

3) f(n)=3(n/4)+2   

Given that f(1)=1 n is divisiable by 2

Take n=4--> f(n)=3 (n/4)+2 -->f(4)=3 (4/4)+2=3(1)+2=3+2=5

a) f(64)=3 (64/4)+2=3(16)+2=48+2=50

b)f(256)=3 (256/4)+2=3(64)+2=192+2=194

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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