Induction proof with handshakes

[nicnicman]

Homework Statement

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)

Homework Equations

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.

 

[clamtrox]

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

 

[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?

 

[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).

 

[D H]

Zero I guess.

Correct. Does P(1)=0 satisfy P(N)=(N²-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)=(N²-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)=(N²-N)/2 valid for N=k+1?

 

[nicnicman]

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

 

[D H]

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

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

 

[clamtrox]

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

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

 

[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.