Exercise 1.4.8 (Dominoes theorem)

Proof.

(a)

To avoid the induction, using Pascal’s relation (1.14), $$\left(\genfrac{}{}{0.0pt}{}{k+m}{k}\right)+\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)=\left(\genfrac{}{}{0.0pt}{}{k+m+1}{k+1}\right),$$

we obtain

$$\begin{array}{llll}\hfill \underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k}\right)& =\underset{m=0}{\overset{M}{\sum }}\left[\left(\genfrac{}{}{0.0pt}{}{k+m+1}{k+1}\right)-\left(\genfrac{}{}{0.0pt}{}{k+m}{k}\right)\right]& \hfill & \\ \hfill & =\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m+1}{k+1}\right)-\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)& \hfill & \\ \hfill & =\underset{n=1}{\overset{M+1}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{k+1}\right)-\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)(n=m+1)& \hfill & \\ \hfill & =\underset{m=1}{\overset{M+1}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)-\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)& \hfill & \\ \hfill & =\left(\genfrac{}{}{0.0pt}{}{k+M+1}{k+1}\right)+\underset{m=1}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)-\underset{m=1}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k+1}\right)-\left(\genfrac{}{}{0.0pt}{}{k}{k+1}\right)& \hfill & \\ \hfill & =\left(\genfrac{}{}{0.0pt}{}{k+M+1}{k+1}\right)& \hfill & \end{array}$$

since $\left(\genfrac{}{}{0.0pt}{}{k}{k+1}\right)=0$. This gives the first proof of

$$\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{m+k}{k}\right)=\left(\genfrac{}{}{0.0pt}{}{k+M+1}{k+1}\right).$$

(b)

Here $𝒮=[[1,k+M+1]]$. For every $m\in [[0,M]]$, consider the set ${𝒞}_m$ of subsets $𝒜$ of $𝒮$ containing $k+1$ elements, with the maximum one being $k+m=1$: $${𝒞}_m=\{𝒜\in {𝒫}_{k+1}(𝒮)\mid \max <!--\; FUNCTION\; APPLICATION\; -->(𝒜)=k+m+1\}.$$

Every $𝒜\in {𝒫}_{k+1}(𝒮)$ has a maximum $m^{\prime }$, where $k+1\le m^{\prime }\le k+M+1$, thus $m^{\prime }=m+k+1$, where $0\le m\le M$. This shows that

$${𝒫}_{k+1}(𝒮)=\underset{m=0}{\overset{M}{\bigcup }}{𝒞}_m.$$

Moreover this union is disjoint: if $𝒜\in {𝒞}_m\cap {𝒞}_n$, then $m=\max <!--\; FUNCTION\; APPLICATION\; -->(𝒜)=n$, thus

$$m\ne n\Rightarrow {𝒞}_m\cap {𝒞}_n=\varnothing .$$

Therefore

$$\begin{array}{lll}\hfill \left|{𝒫}_{k+1}(𝒮)\right|=\underset{m=0}{\overset{M}{\sum }}|{𝒞}_m|.& & \hfill \text{(1)}\end{array}$$

Moreover $\left|{𝒫}_{k+1}(𝒮)\right|=\left(\genfrac{}{}{0.0pt}{}{k+M+1}{k+1}\right)$.

Consider the two maps

$$\phi \{\begin{array}{ccc}\hfill {𝒫}_k([[1,k+m]])\hfill & \hfill \to \hfill & {𝒞}_m\hfill \\ \hfill ℬ\hfill & \hfill \mapsto \hfill & ℬ\cup \{k+m+1\}\hfill \end{array}\psi \{\begin{array}{ccc}\hfill {𝒞}_m\hfill & \hfill \to \hfill & {𝒫}_k([[1,m]])\hfill \\ \hfill 𝒜\hfill & \hfill \mapsto \hfill & 𝒜\setminus \{\max <!--\; FUNCTION\; APPLICATION\; -->(𝒜)\}\hfill \end{array}$$

This makes sense: if $ℬ\in {𝒫}_k([[1,k+m]])$, then $\max <!--\; FUNCTION\; APPLICATION\; -->(ℬ\cup \{k+m+1\})=k+m+1$, where $|ℬ\cup \{k+m+1\})|=k+1$, so $\phi (ℬ)\in {𝒞}_m$, and if $𝒜\in {𝒞}_m$, then $\max <!--\; FUNCTION\; APPLICATION\; -->(A)=k+m+1$, thus $𝒜\setminus \{\max <!--\; FUNCTION\; APPLICATION\; -->(𝒜)\subset [[1,k+m]]$, where $|𝒜\setminus \{\max <!--\; FUNCTION\; APPLICATION\; -->(𝒜)|=k$, thus $\psi (𝒜)\in {𝒫}_k([[1,m]])$.

Moreover, for all $ℬ\in {𝒫}_k([[1,k+m]])$,

$$(\psi \circ \varphi )(ℬ)=(ℬ\cup \{k+m+1\})\setminus \{k+m+1\}=ℬ,$$

and for all $𝒜\in {𝒞}_m$,

$$(\phi \circ \psi )(𝒜)=(𝒜\setminus \{k+m+1)\})\cup \{k+m+1\}=𝒜.$$

Therefore $\psi \circ \phi$ and $\phi \circ \psi$ are identities, thus $\phi$ is bijective, so

$$|{𝒞}_m|=|{𝒫}_k([[1,k+m]])|=\left(\genfrac{}{}{0.0pt}{}{k+m}{k}\right),$$

thus (1) gives

$$\left(\genfrac{}{}{0.0pt}{}{k+M+1}{k+1}\right)=\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{k}\right).$$

This is the second proof.

(c)

Starting from $$\begin{array}{llll}\hfill \frac{1}{{(1-z)}^{k+2}}& =\frac{1}{1-z}\cdot \frac{1}{{(1-z)}^{k+1}},& \hfill & \\ \hfill & & \hfill \end{array}$$

we obtain, using the exercise 1.4.7,

$$\underset{M=0}{\overset{\infty }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+1+M}{M}\right)z^M=\underset{n=0}{\overset{\infty }{\sum }}{z}^n\underset{m=0}{\overset{\infty }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{m}\right)z^m.$$

The absolute convergence of these series for $|z|<1$ (*) gives the Cauchy’s product

$$\begin{array}{llll}\hfill \underset{n=0}{\overset{\infty }{\sum }}{z}^n\underset{m=0}{\overset{\infty }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{m}\right)z^m& =\underset{M=0}{\overset{\infty }{\sum }}\underset{n+m=M}{\sum }\left(\genfrac{}{}{0.0pt}{}{k+m}{m}\right)z^M& \hfill & \\ \hfill & =\underset{M=0}{\overset{\infty }{\sum }}\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{m}\right)z^M.& \hfill & \end{array}$$

The equality of the coefficient of $z^M$ in these two expansions gives

$$\left(\genfrac{}{}{0.0pt}{}{k+1+M}{M}\right)=\underset{m=0}{\overset{M}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+m}{m}\right).$$

This is the third proof.