Prove the Handshake Theorem by induction 
Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.

My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.
For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:

*

*Case 1: The new person's parity is even

*Case 2: The new person's parity is odd


But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.
 A: Equivalently, parities have an even sum. The base step $n=0$ is trivial. Assume $n=k$ works, then add person $k+1$. If they shake hands with $j$ of the first $k$ people, the sum of parities increases modulo $2$ by $j+j=2j=0$.
A: When a new person is added, that person shakes hands with $p$ people and that alter the previous parity.
Assuming the statement true for some k:

*

*There are $k_1$ even people

*There are $k_2$ odd people and $k_2$ mod $2$ = $0$
Adding a new person who shake hands with $p$ people (case $k+1$)

*

*If he shakes hands with $p_1$ even people, that people become odd

*If he shakes hands with $p_2$ odd people, that people become even

*$p_1$ + $p_2$ = $p$
The new number of odd people are:

*

*Case1: $k_2$ - $p_2$ + $p_1$ + 1 if $p$ is odd

*Case2: $k_2$ - $p_2$ + $p_1$ if $p$ is even

By induction hypothesis, $k_2$ is even.
And because $p_1$ - $p_2$ = $p$ - $2p_2$ we can conclude that $p_1$ - $p_2$ = $p$ mod $2$
In both cases, the number of odd people is even.
A: I think your approach is good, and you are almost there.

... the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.


For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well.

Consider a party of $k$ people with $a$ people having even handshake parity and $b$ people having odd parity. By the induction hypothesis, $b$ is even. Then a new person is added and due to their handshakes, $c$ existing guests are changed even to odd and $d$ from odd to even.

*

*Case 1: The new person's parity ($c{+}d$) is even. The new number of odd-parity people is $b{+}c{-}d$. Note that since $c{+}d$ is even, $c{+}d-2d=c{-}d$ is also even. Thus $b{+}c{-}d$ is even as required.


*Case 2: The new person's parity is odd. The new number of odd-parity people is $b{+}c{-}d{+}1$ (the $+1$ for the new person). Now $c{+}d$ is odd, $c{+}d{+}1$ is even and $c{+}d{+}1-2d=c{-}d{+}1$ is also even. Thus the odd parity count $b{+}c{-}d{+}1$ is again even as required.
A: Without induction:
For each person, consider the number of handshakes they participated in. If you add these $n$ numbers, you should get two times the number of total handshakes that occurred (since each handshake is counted twice). Since the sum of these $n$ numbers is an even number, what does that say about the number of odd numbers?
A: The number of participants in a handshake is two.
For any number $n$ handshakes. If we sum the number of times each person has participated in a handshake we will count 2n participations.
Supposing an odd number of people participated in an odd number of handshakes.  The total count of participations will be an odd number.  This contradicts our earlier statement.
If you want a proof by induction.
Base case $n=1$
One person shakes hands with nobody and there are 0 people with an odd number of handshakes.
Suppose for all gatherings of $n$ people our proposition holds.
When the n+1th guest arrives, he has experienced 0 handshakes and our proposition continues to hold.  For each handshake that occurs after this guest's arrival, it changes the parity of both participants.  Number of people who have experienced an odd number of handshakes changes by $0, 2,$ or $-2.$
If our proposition holds for $n$ people it must hold for $n+1$ people.
