Further identities in Pascal’s triangle

Prove identities by equating coefficients of x^r on both sides of an identity such as (1 + x)^n (1 + x)^n = (1 + x)^2n, including the sum of squares of a row, and compare methods of proof.

Equating coefficients

Example 1●●●

Prove that $\left({}^nC_0\right)^2 + \left({}^nC_1\right)^2 + \cdots + \left({}^nC_n\right)^2 = {}^{2n}C_n$.

Start from $(1 + x)^n(1 + x)^n = (1 + x)^{2n}$. On the right, the coefficient of $x^n$ is ${}^{2n}C_n$.

On the left, the coefficient of $x^n$ is ${}^nC_0\,{}^nC_n + {}^nC_1\,{}^nC_{n-1} + \cdots + {}^nC_n\,{}^nC_0$.

Multiply the x^k term of the first bracket by the x^(n−k) term of the second.

That is $\left({}^nC_0\right)^2 + \left({}^nC_1\right)^2 + \cdots + \left({}^nC_n\right)^2$, which proves the identity.

Symmetry: nC(n−k) = nCk.

Example 2●●●

Use $(1 + x)^3(1 + x)^4 = (1 + x)^7$ to show ${}^3C_0\,{}^4C_2 + {}^3C_1\,{}^4C_1 + {}^3C_2\,{}^4C_0 = {}^7C_2$.

Equate the coefficients of $x^2$. On the right: ${}^7C_2 = 21$.

On the left: $1 \times 6 + 3 \times 4 + 3 \times 1 = 21$ ✓

Choosing a method

The identity has	Try
a single sum of ${}^nC_k$ times powers	substitute a value of $x$ (5E)
a factor $k$ in each term	differentiate, then substitute (5E)
products of two coefficients	equate coefficients in a product of expansions
a natural story about choosing	a counting argument

Flashcards

$sum left({}^nC_k ight)^2$

${}^{2n}C_n$

Equating coefficients

Expand both sides of a polynomial identity and match one power of $x$.

Coefficient of $x^r$ in $(1 + x)^m(1 + x)^n$

$\sum_k {}^mC_k\,{}^nC_{r-k} = {}^{m+n}C_r$

Practice

Evaluate $1^2 + 3^2 + 3^2 + 1^2$, the squares of row $3$.
Evaluate $\sum_{k=0}^{4}\left({}^4C_k\right)^2$.
Evaluate ${}^3C_0\,{}^4C_2 + {}^3C_1\,{}^4C_1 + {}^3C_2\,{}^4C_0$.
To prove $\sum \left({}^nC_k\right)^2 = {}^{2n}C_n$, equate the coefficients of $x^n$ in:
Which fact turns ${}^nC_k\,{}^nC_{n-k}$ into $\left({}^nC_k\right)^2$?
The best first attempt at proving $\sum k\,{}^nC_k = n\,2^{n-1}$ is:
In how many ways can $5$ people be chosen from $5$ boys and $5$ girls?
In how many of those ways are exactly $2$ girls chosen?
Find the coefficient of $x^2$ in $(1 + x)^2(1 + x)^2$.