Тотожність Паскаля (різниця) та клюшкова тотожність (сума)

Pascal Triangle and its derived identity

This article seems like to talk about combinatorics, but it is $\textbf{very}$ useful in algebra, since very unexpectedly, you may see lots of symbols or terms related to combinatorics appear in an algebra problem.

First let's have a trivial (maybe not lol) identity, that is THE SYMMETRY IDENTITY. It says for $\forall n,r \in \mathbb{Z},n\geq r\geq 0$ we have

$${n\choose r}={n\choose n-r}$$

This is easy to prove. We know

$${n\choose r}=\frac{n!}{{r!}{(n-r)!}}$$

and

$${n\choose r}=\frac{n!}{(n-r)!r!}$$

Therefore, they are the same. In fact, choosing $r$ winners from a group of $n$ people is the same as choosing $n-r$ losers.

Exercise: Show that ${n\choose 0}={n\choose n}=1$.

Second identity, the summation identity. It says, $\forall n,r\in\mathbb{Z}, n\geq r\geq 0$, $${n\choose r}+{n\choose r+1}={n+1 \choose r+1}$$

This is actually derived from Pascal Triangle

Why I say so, see, every node (ignore the blue dots at the bottom, just look at the points with numbers above) is the sums of pairs of adjacent nodes of the previous row. As an example, 1+2=3 and 4+6=10 in the diagram above. In fact, all numbers can be written in the form of ${n\choose r}$, like $6={4\choose 2}$ and $10={5\choose2} \text{ or } {5\choose3}$, where $n$ represents the $n$-th row and $r$ represents the $r$-th row. In other words, the value at the $n$-th row and the $r$-th row equals to ${n\choose r}$.

For the proof of this identity, it is left as an exercise to the reader. You can use the fact that $${n\choose r}=\frac{n!}{r!(n-r)!}$$

And a problem that I think is a nice application of the summation identity is this. Nice problem, bro!