# Homework Help: Induction proof with handshakes

1. Dec 11, 2012

### nicnicman

1. The problem statement, all variables and given/known data
Suppose that if there are at least 2 people in a room and each person in the room shakes hands with everyone else, but not with himself. Show that the number of handshakes is (n^2-n)/2.
Make sure to show P(1), P(k) and prove P(k+1)

2. Relevant equations

3. The attempt at a solution
Well, I don't have too much yet, but here it is:

Let P(n) be 1 + 2 + 3 + ... + (n - 1) = (n^2-n)/2.

Now, I think I'm going the right direction but when I try to show P(1) I find it doesn't work, because (1^2-1)/2 = 0/2 = 0.

I'm missing something, but I don't know what it is.

Thanks for any suggestions.

2. Dec 11, 2012

### clamtrox

How many ways there are for one person to shake hands with himself? Perhaps you should start with n=2.

3. Dec 11, 2012

### nicnicman

Zero I guess. I think it would be better if I began with 0.

Let P(n) be 0 + 1 + 2 + ... + (n -1) = (n^2-n)/2.

Now, (1^2-1)/2 = 0/2 = 0 and the sum of the first member in the list is 0.

Does that make sense?

4. Dec 11, 2012

### Michael Redei

Your value of 0 in P(1) is quite correct. If one person is alone in the room and he shakes hands "with everyone else, but not with himself", no shaking will be done.

If you want to test the formula (which is correct, by the way), convince yourself by looking at n=2 people or n=3. Another way of getting a grasp on the situation modeled here is to draw n points on a piece of paper (standing for n people) and connecting each pair of points by a line (needn't be straight, it just stands for a handshake).

Draw the whole diagram for n=4 and do some counting. Then add a fifth point and add the necessary lines. You might get an idea about how to prove the step from P(n) to P(n+1).

5. Dec 11, 2012

### D H

Staff Emeritus
Correct. Does P(1)=0 satisfy P(N)=(N2-N)/2 for N=1? If it doesn't, the conjectured relationship is invalid (one way to disprove some supposedly universal conjecture is to find a specific counterexample for which the conjecture is false). On the other hand, if the conjecture is valid for N=1, you have a base case for the induction.

The other half of induction is the inductive step. Assume the relationship is valid for some integer k≥1 and show that this means that the relationship is also true for k+1.

So, suppose that there are some number k≥1 people in the room, all of whom have shaken hands with one another (but not themselves). Assume that the conjectured relationship P(N)=(N2-N)/2 is valid for N=k. Now Bob suppose enters the room and people start shaking hands again.
1. How many more handshakes are needed to satisfy the condition that everyone in the room has shaken hands with everyone else, but not with himself?
2. What is P(k+1) in terms of P(k) and the answer to question #1?
3. Is the conjectured relationship P(N)=(N2-N)/2 valid for N=k+1?

6. Dec 11, 2012

### nicnicman

So, was I correct in beginning with 0 rather than 1. To me, it seems to work better.

7. Dec 11, 2012

### D H

Staff Emeritus
No! You answered the question for N=1, not N=0. More importantly, the problem statement specifically said to start with N=1.

8. Dec 11, 2012

### clamtrox

Well, it also says that there are at least 2 people in the room.

9. Dec 11, 2012

### Michael Redei

The problem statement says there are at least 2 people in the room, but it also tells you to start with P(1). This seems misleading, and I'm sure no one would complain if you include the cases

-- 1 person => 0 handshakes,
-- 1 handshake (2 people),

since either could be meant by "P(1)". For completeness' sake you could also consider the case of zero people, but I'd not go that far.

Proof by induction, $(n!)^{2} \le (2n)!$. Mar 1, 2017