# Number of handshakes in a room

1. Jul 9, 2014

### jonroberts74

1. The problem statement, all variables and given/known data

as each new person arrives to a meeting, they shake hands of all who are present.

prove the number [by induction] of occurred handshakes are $$\frac{n(n-1)}{2}$$

3. The attempt at a solution

if no one shows up then clearly no handshakes are exchanged

$$\frac{0(0-1)}{2} = 0$$

assuming k people show up, there will be $$\frac{k(k-1)}{2}$$ handshakes

now if one more person shows up, that will make a total of k+1 people and because one does not shake their own hand there will be k +1 -1 more shakes than when there where k people .

there will be

$$\frac{(k+1)(k+1-1)}{2}$$ handshakes in total

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

is this explained properly?

2. Jul 9, 2014

### LCKurtz

I don't follow that step. Aren't you assuming what you are trying to prove?

3. Jul 9, 2014

### jonroberts74

I felt like I was assuming but wasn't for sure.

I feel like theres a point where I need to state the new number of handshakes with each incoming person is the new total of people minus 1, so I don't know if I said that at the right time.

4. Jul 9, 2014

### LCKurtz

If there are $k$ people in the room your induction hypotheses says there have been $\frac{(k-1)(k)}{2}$ handshakes. If you now walk into the room, how many handshakes will you add (easy question)?

5. Jul 9, 2014

### jonroberts74

so start here

$$\frac{k(k-1)}{2} + k$$

6. Jul 9, 2014

### LCKurtz

Yes. Simplify that and see if you get the right formula for $k+1$. You worked it backwards originally.

7. Jul 9, 2014

### thelema418

In addition to above, I'm concerned about the basis case, $n = 0$. In the context of the problem, I'm wondering why you did not chose $n = 1$ or $n = 2$.

8. Jul 9, 2014

### thelema418

More explicitly: make certain that the inductive step works when $k = 0$ in the steps LCKurtz mentioned

9. Jul 9, 2014

### HallsofIvy

Staff Emeritus
I would have stated this a little differently. If one more person arrives he must shake hands witheach of the k people who were already there so the number of handshakes is increased by k:
$$\frac{k(k-1)}{2}+ k$$

10. Jul 9, 2014

### LCKurtz

Apparently you didn't read posts 4, 5, and 6?

11. Jul 9, 2014

### jonroberts74

I didn't notice them, rereading all now

nvm, not to me.

so many long days, haha

Last edited: Jul 9, 2014
12. Jul 10, 2014

### HallsofIvy

Staff Emeritus
Of course this can be done more simply without induction. Each of the n people must shake hands with each of the n-1 others which would give n(n-1) people shaking hands. But each hand shake involves 2 people so that is n(n-1)/2 hand shakes.