Solutions

(a) Let's begin by applying the suggested hint.

$$\begin{aligned} {(1 + x)}^{n} ({1 + x})^{m} &= \sum_{i = 0}^{n} {n\choose{i}} x^{i} 1^{n - i} \sum_{j = 0}^{m} {m\choose{j}} x^{j} 1^{m - j} \\ &= \sum_{i = 0}^{n} {n\choose{i}} x^{i} \sum_{j = 0}^{m} {m\choose{j}} x^{j} \\ &= ( {n\choose{0}} + {n\choose{1}}x^{1} + \dots + {n\choose{n}}x^{n} ) \\ & \quad \times ( {m\choose{0}} + {m\choose{1}}x^{1} + \dots + {m\choose{m}}x^{m} ) \end{aligned}$$

Notice, also, that ${(1 + x)}^{n}{(1 + x)}^{m} = {(1 + x)}^{n + m}$. Thus,

$$\begin{aligned} {(1 + x)}^{n} ({1 + x})^{m} &= {(1 + x)}^{n + m} \\ &= \sum_{l = 0}^{n + m} {n + m \choose{l}} x^{l} \\ &= {n + m \choose{0}} + {n + m \choose{1}} x^{1} + \dots + {n + m \choose{n + m}}x^{n + m} \end{aligned}$$

Now, by applying distributivity on the first equation:

$$\begin{aligned} ( & {n\choose{0}} + {n\choose{1}}x^{1} + \dots + {n\choose{n}}x^{n} ) \times ( {m\choose{0}} + {m\choose{1}}x^{1} + \dots + {m\choose{m}}x^{m} ) \\ &= {n\choose{0}} ({m\choose{0}} + \dots + {m\choose{m}}x^{m}) + \dots + {n\choose{n}} ({m\choose{0}} + \dots + {m\choose{m}}x^{m}) \\ &= ({n\choose{0}} {m\choose{0}}) + ( {n\choose{0}} {m\choose{1}}x^{1} + {n\choose{1}}x^{1} {m\choose{0}}) + \dots + ({n\choose{n}}x^{n} {m\choose{m}}x^{m} ) \\ &= ({n\choose{0}} {m\choose{0}}) + ( {n\choose{0}} {m\choose{1}} + {n\choose{1}} {m\choose{0}})x^{1} + \dots + {n + m \choose{n + m}}x^{n + m} \end{aligned}$$

By equating the two, we obtain:

$$\begin{aligned} ( & {n\choose{0}} {m\choose{0}}) + ( {n\choose{0}} {m\choose{1}} + {n\choose{1}} {m\choose{0}})x^{1} + \dots + {n + m \choose{n + m}}x^{n + m} \\ &= {n + m \choose{0}} + {n + m \choose{1}} x^{1} + \dots + {n + m \choose{n + m}}x^{n + m} \\ &\implies \sum_{k = 0}^{l} {n\choose{k}} {m\choose{l - k}} = {n + m \choose{l}} \end{aligned}$$

(b)

$$\begin{aligned} {2n\choose{n}} &= {n + n \choose{n}} \\ &= \sum_{k = 0}^{n} {n\choose{k}} {n\choose{n - k}} && (a) \\ &= \sum_{k = 0}^{n} {n\choose{k}}^{2} && {n\choose{k}} = {n\choose{n - k}} \end{aligned}$$