For integers $k$ and $n$ with $0 \leqslant k \leqslant n$, define $\left(\begin{array}{l}n \\ k\end{array}\right)$. Arguing from your definition, show that

$$\left(\begin{array}{c} n-1 \\ k \end{array}\right)+\left(\begin{array}{l} n-1 \\ k-1 \end{array}\right)=\left(\begin{array}{l} n \\ k \end{array}\right)$$

for all integers $k$ and $n$ with $1 \leqslant k \leqslant n-1$.

Use induction on $k$ to prove that

$$\sum_{j=0}^{k}\left(\begin{array}{c} n+j \\ j \end{array}\right)=\left(\begin{array}{c} n+k+1 \\ k \end{array}\right)$$

for all non-negative integers $k$ and $n$.