Prove number of handshakes between $n$ people is $\tfrac{n(n−1)}{2}$ by induction

Question

How do we calculate the number of handshakes between $n$ people? And where do I apply the inductive step?

Answer 1

One way to do this is by drawing $n$ number of points and connecting all the points together using lines; the number of lines drawn would be the number of handshakes needed.

For example for $2$ points, in order to connect them you'd need a single line.

For $3$ points $A$, $B$, and $C$, you'd need one line to connect $A$ to $B$, a second line to connect $B$ and $C$, and a third to connect $C$ to $A$. Notice that if you plug in $n=3$ into the formula you'd get:

$$\begin{align} \frac{3(3-1)}{2} & = \frac{3(2)}{2} \\ & = \frac{3(1)}{1} \\ & = 3\end{align}$$

Which is exactly the number of lines drawn!

Try this for a square and a pentagon, though it gets harder as you add more and more points.

Answer 2

Suppose $k$ people shake hands. Your induction hypothesis then is that there are $\frac{k(k-1)}{2}$ handshakes.

Now suppose you have one more person, so you have $k+1$ people. This new person will shake hands with all the other $k$ people there, so now the number of handshakes will be $\frac{k(k-1)}{2} + k$. But if your general claim about the number of handshakes among $n$ people is correct, we should have that this number obeys the formula in the claim. I.e., $$ \frac{k(k-1)}{2} + k = \frac{(k+1)\big((k+2)-1\big)}{2} $$ Can you show that this is true?

Answer 3

between 2 people there's only one handshake happens..@Aldon but I'm also not sure how to this prove, it's not $n=n(n-1)/2$ for sure.

for $n=2$ number of handshakes is $1$

for $3$ it's $3$

for $4$ it's $6$

for $5 $ it's $10$

Answer 4

This would normally be calculated as $\pmatrix{n\\2}$ where $n$ is the number of handshakes.

We know the following:

$$\pmatrix{n\\2}=\sum_{i=1}^{n-1}i$$

With the latter, we use Gauss' Method to obtain the following:

$$\frac{(n-1)([n-1]+1)}{2}\equiv \frac{(n-1)(n)}{2}$$

Which matches your solution.

In simpler terms, imagine drawing an arrangement of $n$ dots. Connect each dot to each other dot with a line (representing a handshake). If you have 8 dots, start with one at random. Notice that you can draw exactly one line between it and the other seven dots (i.e. seven lines). Pick a second dot, and you'll notice that you can only do six lines, since there's already one between dots one and two. Repeat this and you will soon see that your total is the following sum:

$$\sum_{i=1}^{n-1}i$$

Once you see this, refer to the non-inductive approach above.

Answer 5

I'm not sure my first instinct would be to do induction. I'd simply think each $n$ people shake hands with $n -1$ everyone else for $n(n -1)$ handshakes if you count Ann's handshake with Bob separately from Bob's handshake with Ann. But since you don't and there are 2 people to a handshake it $n(n-1)/2$ handshakes.

But since the problem is to do it by induction:

Assume $n$ people have $n(n -1)/2$ handshakes. Lets suppose you have $n$ people and they've all shook hands with each other (so there have been $n(n-1)/2$ handshakes). Imagine a new person comes in. He must now shake hands with everybody. That's $n$ more handshakes or $n(n-1)/2 + n$ handshakes total.

$\frac {n(n-1)} 2 + n = \frac {n(n-1) + 2n}{2} = \frac {n^2 + n}{2} = \frac {n(n+1)} 2 = \frac {(n+1)(n+1 -1)}{2}$

So that's the inductive step.