In this problem, construct a bijection to show the identity. Use the definitions of these quantities, not formulas for them.
For $0≤j≤n$ $$\binom{n}{j}=\binom{n}{n-j}$$
I know how to prove this by induction, but I have no idea what "construct a bijection" stands for. Could anyone explain this or (better) show me an example? Thanks.
On
A bijection is a one-to-one correspondence between sets. If there is a bijection between two sets they have the same cardinal size (which, for finite sets that is basically: "count of elements").
In this case, $\binom n j$ is the count of ways to select $j$ elements from a set of size $n$.
Meanwhile, $\binom n {n-j}$ is the count of ways to select $n{-}j$ elements from a set of size $n$.
Let us call $N$ the set of $n$ items. Let $J$ be the set of sets of size $j$ that can be selected from $N$. Let $K$ be the set of sets of size $n-j$ that can be selected from $N$.
Show that there is a bijection from $J\mapsto K$. If the sets have the same size then the above counts have the same value.
Well, for any set in $J$ there is a single $N$-relative complement of size $n-j$. ...
Consider the number of ways to arrange $n$ bits, $j$ of which are ones; by definition there are $\binom nj$ ways of doing so. For every such way we can flip the bits to obtain an arrangement of $n$ bits where $n-j$ of them are ones; there are $\binom n{n-j}$ arrangements here. For example:
This flipping of bits constitutes the bijection. Since every way of arranging the bits is accounted for on both sides of the bijection, this shows that $\binom nj=\binom n{n-j}$.