Suppose we have $n+1$ items. The last item is special.
We can think of $\binom{n}{k-1}$ as counting the number of ways to pick $k-1$ items out of the first $n$. This is the same as the number of ways to pick $k$ items out of $n+1$ in a way that includes the last item.
We can think of $\binom nk$ as counting the number of ways to pick $k$ items out of the first $n$. This is the same as the number of ways to pick $k$ items out of $n+1$ in a way that does not include the last item.
Since $k \le \lfloor \frac n2 \rfloor$, we have $k < \frac{n+1}{2}$, so we are picking fewer than half of the $n+1$ items. This means we should include the special, last item less than half the time: so $\binom{n}{k-1}$ (which counts the cases when we include it) should be less than $\binom{n}{k}$ (which counts the cases when we don't).
Using a sign-reversing involution is a common way to give a combinatorial proof of equations involving a summation with alternating sign.
A
I can do no better than to quote this answer directly: https://math.stackexchange.com/a/3401952/499816
I'll present a proof using the "Description, Involution, Exception" technique of A. Benjamin and J. Quinn to simplify the left side. Consider counting pairs $(A, B)_k$, where each item is a size-$k$ subset of $\{1, 2, \dots, 2n\}$. Clearly for each $k$ the total number of such pairs is $\binom{2n}{k}^2$.
Our involution, then, is to take the smallest element either in both sets or neither set, and either remove it from both or add it to both respectively. It should be clear that this is an involution, and that an element and its image are always counted at different parities in our summation, and thus contribute 0 to the total sum.
So, the elements not cancelled by this involution are exactly those pairs which are disjoint and whose union is all $2n$ elements. Being disjoint means having size no more than $n$, by pigeonhole, and totaling $2n$ means having at least $n$ each. Thus this is exactly the $n$-element pairs that have no overlap, which can be counted by choosing $n$ elements for the left item (as the right item must have exactly the rest). Meanwhile, the sign is inherited from the larger summation, where it is based on the parity of $k$, here $n$. This gives us $(-1)^n\binom{2n}{n}$.
C
For this, we can also use a sign-reversing involution. Consider counting the number of ways to tile a $1\times n$ rectangle with $1\times 1$ squares, where each square can be either white or black, and with $1\times 2$ dominos, where the dominos only come in one color. If you use $k$ dominos, then there will be $n-2k$ squares, so $n-k$ tiles total. There are $\binom{n-k}k$ ways to choose the locations of the dominos, and then $2^{n-2k}$ ways to choose the colors of the squares. The parity of a tiling is determined by the parity of the number of dominos.
The sign-reversing involution is to find the first instance of either a domino, or a white square immediately followed by a black square. If the first is a domino, then you replace that domino with a white square followed by a black square, and if it is a white square followed by a black square, you replace those two squares with a domino. The only tilings are not canceled out are the ones without dominos, and without any white squares immediately followed by black squares. There are $n+1$ such exceptional tilings, namely the tilings which are $j$ black squares followed by $n-j$ white squares, for each $j\in \{0,1,\dots,n\}$.
B
For this, we use an inclusion-exclusion argument. Both sides answer the following question.
There is an $m\times n$ grid of squares. How many ways are there to shade in exactly $n$ squares of the grid so that every column has at least one shaded square?
The easy answer is $m^n$; each column gets exactly one shaded square, and there are $m$ squares in each of the $n$ columns.
To explain the alternating sum, let $U$ be the set of ways to shade in $n$ squares of the grid, without the column restriction, so $|U|=\binom{mn}{n}$. For each $i\in \{1,\dots,n\}$, let $S_i$ be the set of colorings in $U$ where the $i^{th}$ column is unshaded. We are trying to count $|S_1^c\cap S_2^c\cap \dots \cap S_n^c|$. Using the principle of inclusion-exclusion, the answer is
$$
\sum_{k=0}^n(-1)^k\binom{n}{k}|S_1\cap \dots \cap S_k|,
$$
provided that when $k=0$, you interpret the empty intersection as $|U|$. It should be clear that $|S_1\cap \dots \cap S_k|=\binom{m(n-k)}n$, since the $n$ shaded squares can be freely chosen from the remaining $n-k$ columns. Plugging that in above and reversing the order of summation leads to desired summation, completing the proof.
Best Answer
The bijective argument for all $p$ is the following. Write $n = ap + b$ where $0 \le b \le p-1$, so that $a = \lfloor \frac{n}{p} \rfloor$. Divide the set $[n] = \{ 1, 2, \dots n \}$ into $a$ groups of $p$ elements and $b$ elements left over. Consider the action of the cyclic group $C_p$ on the set of $p$-element subsets of $n$ by cyclic permutation on each of the $a$ groups of $p$ elements. There are two kinds of orbits, orbits of size $p$ and fixed points, so ${n \choose p}$ is congruent $\bmod p$ to the number of fixed points. And the fixed points are exactly given by the $a$ groups of $p$ elements themselves, of which there are $a = \lfloor \frac{n}{p} \rfloor$.
A generalization of this argument proves that
$${ap + b \choose cp + d} \equiv {a \choose c} {b \choose d} \bmod p$$
and iterating this identity proves Lucas' theorem
$${\sum a_i p^i \choose \sum b_i p^i} \equiv \prod {a_i \choose b_i} \bmod p$$
where $a_i, b_i$ are digits in base $p$; this can also be proven directly with a similar argument. You can see several other arguments like this at this blog post, including a bijective proof of Fermat's little theorem and Wilson's theorem.
An important corollary of this result is that if $p^k$ is the largest power of $p$ dividing $n$ then ${n \choose p^k}$ is not divisible by $p$ (which also follows from Kummer's theorem). This fact can famously be used to prove the first Sylow theorem.
Edit: Stripping out the group theory, here is the argument specialized to the case $p = 3$ for concreteness but there's nothing special about $3$ here. Write $n = 3a + b$ where $0 \le b \le 2$. Divide the set $[n] = \{ 1, 2, \dots 3a + b \}$ into $a$ groups of $3$ elements
$$\{ 1, 2, 3 \}, \{ 4, 5, 6\}, \dots \{3a-2, 3a-1, 3a \}$$
together with $b$ leftover elements $\{ 3a+1, \dots 3a+b \}$. Now we are going to group together the $3$-element subsets of $\{ 1, 2, \dots 3a+b \}$ as follows:
The general result, again stripped of any explicit references to group theory, is the following. Suppose $p$ is a prime, $X$ is a finite set, and $f : X \to X$ is a permutation such that $f^p(x) = x$ for all $x \in X$. Then $X$ splits up as the disjoint union of the fixed points of $f$ together with subsets of size $p$ of the form $\{ x, f(x), f^2(x), \dots f^{p-1}(x) \}$; in particular, $|X|$ is congruent to the number of fixed points of $f$, $\bmod p$.