1. Math
  2. Advanced Math
  3. explain in words why each recurrence relation is represented by...

Question: explain in words why each recurrence relation is represented by...

Question details

Explain in words why each recurrence relation is represented by the given description. (You do not need to solve the recurrence.) For example: H(2) = 1 H(n) = H(n-1) + n-1 for n-3 H(n) is the number of handshakes in a room of n people where everybody shake hands with everybody else exactly once. ou could say: If there are two people in the room then there is only one handshake so P(2) -1. Lets say that I am one of the n people. We can divide the set of handshakes into two categories, the handshakes that I made and the handshakes that I did not make. I made n- 1 handshakes. The handshakes that I did not make were all the handshakes between the other n - 1 people as if I had not been there, so there are H(n -1) handshakes that I did not make. Therefore: H(n)-H(n -1) + n-1 C(1) = 0. C(2) = 0. C(3) = 1. C(4) = 1 C(n) = C(n-3) + C(n-1) for n > 5 C(n) is the number of sequences of 3s and 4s 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 n23 B(n) is the number of n-bit binary strings that avoid 000.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution