Mathematical Induction Problem?

1

BASE CASE:

First you must prove the base case with 2 people. We know that 2 people will result in 1 handshake. Confirm that it works for n = 2:

(n² - n) / 2

= (2² - 2) / 2

= (4 - 2) / 2

= 2/2

= 1 handshake

INDUCTION STEP:

Start with n people in the room (n > 1) and assume they have all shaken hands with everyone else for a total of (n² - n) / 2 handshakes.

Now add 1 more person to the room. That person must shake hands with the n people already in the room. So for n+1 people it is (n² - n)/2 + n

Now let's see if we can get it in the right form to prove this; begin by getting a common denominator:

(n² - n) / 2 + 2n/2

= (n² + 2n - n) / 2

We know we want (n+1)² in there, so let's add and subtract a 1, inside the parentheses:

= (n² + 2n + 1 - n - 1) / 2

Next let's factor the first 3 terms into a perfect square:

= ((n + 1)(n + 1) - n - 1) / 2

= ((n + 1)² - n - 1) / 2

Almost there:

= ((n + 1)² - (n + 1)) / 2

This is the correct form, if we plug in k = n+1:

= (k² - k) / 2

So we proved it for the base case of n = 2, then proved the induction step, so it follows for all n > 1.