plain in words why each recurrence relation is represented by the given descript
ID: 2928337 • Letter: P
Question
plain in words why each recurrence relation is represented by the given description For example P(1) = 2 P(n) = P(n-1) +2 for n>2 P(n) slices after cutting a pizza n times along a diameter you could say: There are two halves of the pizza after one cut so P(1) = 2 After n-1 cuts, you have P(n-1) slices, if you slice one more time (the nth time), you will cut two of the slices in half creating two more slices so P(n) = P(n-1) +2. H(2) = 1 H(n) = H(n-1) + n-1 for n23 H(n) is the number of handshakes in a room of n people where everybody shake hands with everybody else exactly once. C(1) = 0, C(2) = 0, C(3) = 1, C(4) = 1 C(n) = C(n-3) + C(n-4) for n 5 C(n) is the number of sequences of 3's and 4's that add up to n. B(1) = 2, B(2) = 4, B(3-7 B(n) = B(n-1) + B(n-2) + B(n-3) for n > 3 B(n) is the number of n-bit binary strings that avoid 000 F(1-0 F(n) = 2F(n/2) + 1 for n 1 F(n) is the number of matches played in a single elimination tournament with n players (you can assume n 2k for some positive integer k. You can use the bracket below to help explain.) 16 Team Single Himinatiorn WinnerExplanation / Answer
a) Number of handshakes between 2 people can be only 1
Therefore H(2)=1
Number of handshakes between 3 people is 3
Number of handshakes between 4 people is 6
This can be also represented as 3+4-1 or H(3)+4-1 or H(n-1)+n-1
c)
N Bit binary srings that avoid 0
B(1)= 2^1=2 but they are 1 and 0 and we have to avoid 0 so B(1)=1
B(2)=2^2=4
B(3)=2^3=8 but we aviod 0 therefore 8-1=7
B(4)=2^4=16 but avoid 3 zeros therefore B(4)=13=B(3)+B(2)+B(1)
d)
n=2^k
F(1)=2^0 Therefor 0
F(2)=2^1=0+1
=2F(1)+1
=2F(2/2)+1
Therefore F(n)=2F(n/2)+1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.