Understanding the Handshake Problem I need help with this problem. The problem goes like this: In some countries it is customary to shake hands with everybody in the meeting. If there are two people there is 1 handshake, if there are three people there are three handshakes and so on. I know that the formula is $ \dfrac{n(n-1)}{2} $ but how do I get to this solution using a thinking process, specifically how would you solve this? Thanks.

What you can do is induction : You want to know that, if there are $n$ people at meeting, there will be
$$
\frac{1}{2}n(n-1)
$$
handshakes.
You have already established this for $n=2$, so suppose it is true when $n=k-1$, and you want to establish it for $n=k$. Now you know that, with $k-1$ people in the room, there are
$$
\frac{1}{2}(k-1)(k-2)
$$
handshakes. If 1 person enters the room, he/she shakes hands with each person in the room, adding $(k-1)$ handshakes to the total. This gives
$$
\frac{1}{2}(k-1)(k-2) +(k-1) = (k-1)\frac{(k-2) + 2}{2} = \frac{1}{2}k(k-1)
$$
handshakes.
Thus, by induction, you have established it for all $n\in \mathbb{N}$.
