2項係数の2重和の問題

\begin{align*} \sum_{k=0}^{n}C\left(n,k\right)\sum_{j=k}^{n}C\left(n+1,j+1\right) & =\sum_{k=0}^{n}C\left(n,k\right)\sum_{j=0}^{n-k}C\left(n+1,j+k+1\right)\\ & =\sum_{k=0}^{n}C\left(n,k\right)\sum_{j=0}^{n-k}C\left(n+1,n-j+1\right)\\ & =\sum_{k=0}^{n}C\left(n,k\right)\sum_{j=0}^{n-k}C\left(n+1,j\right)\\ & =\sum_{k=0}^{n}C\left(n,k\right)\sum_{j=k}^{n}C\left(n+1,j-k\right)\\ & =\sum_{k=0}^{n}C\left(n,k\right)\sum_{j=k}^{n}\left\{ C\left(n,j-k\right)+C\left(n,j-k-1\right)\right\} \\ & =\sum_{j=0}^{n}\sum_{k=0}^{j}C\left(n,k\right)\left\{ C\left(n,j-k\right)+C\left(n,j-k-1\right)\right\} \\ & =\sum_{j=0}^{n}\left\{ C\left(2n,j\right)+C\left(2n,j-1\right)\right\} \\ & =\sum_{j=0}^{n}C\left(2n+1,j\right)\\ & =\frac{1}{2}\left\{ \sum_{j=0}^{n}C\left(2n+1,j\right)+\sum_{j=0}^{n}C\left(2n+1,j\right)\right\} \\ & =\frac{1}{2}\left\{ \sum_{j=0}^{n}C\left(2n+1,j\right)+\sum_{j=0}^{n}C\left(2n+1,2n+1-j\right)\right\} \\ & =\frac{1}{2}\left\{ \sum_{j=0}^{n}C\left(2n+1,j\right)+\sum_{j=0}^{n}C\left(2n+1,2n+1-\left(n-j\right)\right)\right\} \\ & =\frac{1}{2}\left\{ \sum_{j=0}^{n}C\left(2n+1,j\right)+\sum_{j=0}^{n}C\left(2n+1,n+1+j\right)\right\} \\ & =\frac{1}{2}\left\{ \sum_{j=0}^{n}C\left(2n+1,j\right)+\sum_{j=n+1}^{2n+1}C\left(2n+1,j\right)\right\} \\ & =\frac{1}{2}\sum_{j=0}^{2n+1}C\left(2n+1,j\right)\\ & =\frac{1}{2}\cdot2^{2n+1}\\ & =4^{n} \end{align*}