Question

In each situation, write a recurrence relation, including base case(s), for the given function. briefly explain in words why this recurrence describes the situation. you do not need to solve the recurrence (that is, get a closed-form formula). (a) in a round-robin thumb-wrestling tournament with n people, everybody thumb-wrestles with everybody else. let t(n) be the total number of thumb-wrestling matches taking place among the n people. write a recurrence for t(n).

Answer 1

A thumb-wrestling match requires two thumbs, so we can either suppose that we need at least two people $(n\ge2)$, or allow one to thumb-wrestle one's self. In either case, we'd have $t(1)=t(2)=1$, so let's just say we need a minimum of two players.

If we add one more person to the set of players, then the first two people would need to play 1 additional match each. So $t(3)=t(2)+2$.

If we add one more person, then the first three people would again each have to play 1 more match with the new person. So $t(4)=t(3)+3$.

And so on, so that in general, the number of games needed for everyone to play exactly one match with everyone else is given recursively by

$\begin{cases}t(2)=1\\t(n+1)=t(n)+n&\text{for }n\ge2\end{cases}$