この総和ってどうやって計算するのですか？

幾何学のことばを借りて問題を言い換えます。

・$f(x,y) := {}_n\mathrm{C}_x \cdot {}_{n + 1}\mathrm{C}_y$，

・$xy$ 平面上の領域 $0 \leqq x \leqq n,\ x + 1 \leqq y \leqq n + 1$ 内の格子点全体を $A$

とおけば，求めるべき和は

$$S_1 = \sum_{(x,y) \in A} f(x,y)。$$

この $S_1$ を直接計算することは出来そうにないので，別の未知数を導入して連立方程式を立てることを考えます。

【立式 $1$】

領域 $0 \leqq x \leqq n,\ 0 \leqq y \leqq x$ 内の格子点全体を $B$ として，

$$S_2 = \sum_{(x,y) \in B} f(x,y)$$

とおけば，

$$S_1 + S_2 = \sum_{0 \leqq x \leqq n} \sum_{0 \leqq y \leqq n + 1} f(x,y) = 2^{2n + 1}。$$

【立式 $2$】

$f(x,y)$ がもつ次の性質に注目。

$$f(x,y) = f(n - x, y), \quad f(x,y) = f(x, n + 1 - y)$$

これは $f$ の値が鏡映変換 $(x,y) \mapsto (n - x, y)$ および $(x,y) \mapsto (x, n + 1 - y)$ の前後で変わらないことを意味する。だから，$2$ つの鏡映をたて続けにおこなう変換

$$T(x,y) = (n - x, n + 1 - y)$$

の前後でも $f$ の値は変わらない。つまり，$f(x,y) = f(T(x,y))$。

　図を描いて $T$ の振る舞いをイメージしてみると察しがつくように，$T$ は $A$ の点を $B$ の点へ移す。実際，

$$\begin{aligned}& T(x,y) \in B \\&\quad\iff (n - x, n + 1 - y) \in B \\&\quad\iff 0 \leqq n - x \leqq n\ かつ\ 0 \leqq n + 1 - y \leqq n - x \\&\quad\iff 0 \leqq x \leqq n\ かつ\ x + 1 \leqq y \leqq n + 1 \\&\quad\iff (x,y) \in A\end{aligned}$$

だから，$x \in A$ ならば $T(x,y) \in B$。

　鏡映変換は一対一の変換だから，それを立て続けにおこなう $T$ もまた一対一の変換である（※平行でない $2$ 直線に対する鏡映変換の積だから実は回転変換。）つまり，$T$ は $A,B$ の元を一対一に対応づけるので，

$$\begin{aligned} S_1&= \sum_{(x,y) \in A} f(x,y) = \sum_{(x,y) \in A} f(T(x,y)) \\&= \sum_{(x,y) \in B} f(x,y) = S_2。\end{aligned}$$

以上で得た $2$ 式から，

$$\begin{aligned}2S_1 &= 2^{2n + 1} \\\therefore\ S_1 &= 4^n。\end{aligned}$$

を得ます。