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.

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.
