View Full Version : Math Induction HW

10-05-2003, 11:22 PM
hey all,

I'm on my last problem and I'm stuck. I think it is just too late, but i desperately want to finish this today. Anyhow here is what it reads:

In any group of k people, k>=1, each person is to shake hands with every other person. Find a formula for the number of handshakes, and prove the formula using induction.

Once i get the formula the proof is cake, but the formula is driving me crazy, and it is probably very simple.

so here is what I have

1 person = 0 shakes
2 people = 1 shake
3 people = 3 shakes
P(4) = 6
P(5) = 10
P(6) = 15
...and so on

can anyone put me on the right track?



10-05-2003, 11:53 PM
I finally found the formula so please disregard this post!

for all interested here it is: k( k -1 ) / 2 for k >=1

so simple!!!:o :o and it took an hour of my life

10-05-2003, 11:54 PM
Damn i was alogn those lines workign on it, ah well shoulda given me another 5 minutes

10-06-2003, 12:12 AM
thanks anyways: if you want I have one for extra credit, here goes:

A simple closed polygon consists of n points in the plane joined in pairs by n line segments: each point is the endpoint of exactly two line segments. Use the first and second principal of induction to prove that the sum of the interior angles of an n-sided closed polygon is ( n - 2 ) 180degrees for all n >= 3.

I'll work on this one now, until I'm too sleepy to do anymore.

10-06-2003, 12:31 AM
well, this one was fairly simple...the proof below is using the second principal of induction:

when k = 3, we have a triangle. Sum of all angles = 180 so
for each n > 3, if P(k) is true for all k with 3 <= k < n, then P(n) is true.

180(k-2) + 180[(n-k+2)-2] = 180(k-2) +180(n-k)
= 180[(k-2) + (n-k)]
= 180(n-2) => DONE

basically you can divide each k-sided polygan with k-3 lines to form
triangles. Multiply the number of triangles by 180....simple