For this question, $\left({n\choose k}\right)$ denotes the number of multisets of size $k$ with elements from $[1,\cdots, n].$ For instance, there are $3$ multisets of size $2$ from the set $[1,2],$ namely $[1,2],[1,1],$ and $[2,2].$ Here, the notation $[\cdot]$ and $\{\cdot\}$ is just used to distinguish multisets from regular sets. $[1,2] = \{1,2\}$ but $[1,1] \neq \{1,1\} = \{1\}.$ Prove that $\left({n\choose k}\right) = \sum_{j=0}^k \left({n-1\choose j}\right)$.
Let $S$ represent the set of multisets of size $k$ from $[1,\cdots, n], S_j$ represent the set of subsets of size $j$ from $\{1,\cdots, n\}, T_{k-j}$ represent the set of multisets of size $k-j$ from $S_j$, and $U_j$ represent the set of multisets of size $k$ with $j$ distinct elements from $[1,\cdots, n]$. We have that $|S| = \left({n\choose k}\right)$. Observe that $|S_j| = {n\choose j}$ and $|T_{k-j}| = \left({j\choose k-j}\right)$. Observe that each $k$-multiset of $[1,\cdots, n]$ has between $1$ and $k$ distinct elements. We have that $U_0 = \emptyset$, so $S = \cup_{j=0}^k U_j$. I know how to find a bijection $f \colon U_j \to S_j\times T_{k-j}$ to show that the sets have the same cardinality. This, coupled with the fact that the $U_j$s are disjoint, shows that $|S| = \sum_{j=0}^k |U_j| = \sum_{j=0}^k {n\choose j}\left({j\choose k-j}\right)$.
Is this correct?