Free preview

27 lessons

Essential Probability & Statistics for ML

Free preview

Essential Probability & Statistics for ML · 27 lessons

Master the fundamentals

No surprise gaps

Actually remember it

Skip what you know

One subscription. All learning paths included.

Our content is best on a larger screen

Sums of binomial coefficients

Sums with one power

Explanation

The binomial theorem

(x + y)^n = \sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}

holds for any numbers $x$ and $y$ . If we set $x = 1$ and $y = 1$ , every term reduces to its coefficient, since $1^k = 1$ and $1^{n-k} = 1$ , so

\sum_{k=0}^{n}\binom{n}{k} = 2^n

That is, adding up the number of subsets of each size gives $2^n$ . This makes sense: $\binom{n}{k}$ counts the subsets of size $k$ of a set with $n$ elements, and that set has $2^n$ subsets in all.

Keeping $y = 1$ but choosing any number for $x$ works the same way:

Sums with one power

Theorem

For any number $x$ and any positive integer $n$ ,

\sum_{k=0}^{n}\binom{n}{k}x^k = (x + 1)^n

Note that $x$ can be negative. Setting $x = -1$ gives the alternating sum

\sum_{k=0}^{n}(-1)^k\binom{n}{k} = (-1 + 1)^n = 0

Example

Evaluate $\displaystyle\sum_{k=0}^{4}\binom{4}{k}3^k$ without adding the terms.

Solution

We match the general term of the sum to the general term of the theorem:

In the theorem	In this sum	So
$\binom{n}{k}$	$\binom{4}{k}$	$n = 4$
$x^k$	$3^k$	$x = 3$
$y^{n-k}$	none	$y = 1$

A missing factor means that number is $1$ , since every power of $1$ is $1$ .

So the sum equals

(3 + 1)^4 = 4^4 = 256

Practice questions

4 questions

What is the value of $\displaystyle\sum_{k=0}^{5}\binom{5}{k}$ ?

Select the correct answer:

$32$

$25$

$10$

$64$

+ 3 more questions

Sums with two powers

Explanation

We can use the binomial theorem to evaluate sums that have the same form as its expansion. To see how, consider

\sum_{k=0}^{2}\binom{2}{k}3^k2^{2-k}

We match its general term to the general term of the theorem,

\binom{n}{k}x^ky^{n-k}

and see that $n = 2$ , $x = 3$ and $y = 2$ , so the sum is $(3 + 2)^2 = 25$ .

The same works for any sum of this form.

Evaluating a sum of binomial coefficients

Procedure

Match the general term to $\binom{n}{k}x^ky^{n-k}$ : $x$ is the number whose power counts up with $k$ , and $y$ is the number whose power counts down. A missing factor means that number is $1$ .
The sum equals $(x + y)^n$ . Evaluate that single power.

Later we will meet probabilities of the form $\binom{n}{k}p^k(1 - p)^{n-k}$ , where $p$ is a probability between $0$ and $1$ . A sum of these terms has the same form, with $x = p$ and $y = 1 - p$ .

Example

Evaluate $\displaystyle\sum_{k=0}^{3}\binom{3}{k}2^k3^{3-k}$ without adding the terms.

Solution

We match the general term of the sum to the general term of the theorem:

In the theorem	In this sum	So
$\binom{n}{k}$	$\binom{3}{k}$	$n = 3$
$x^k$	$2^k$	$x = 2$
$y^{n-k}$	$3^{3-k}$	$y = 3$

So the sum equals

(2 + 3)^3 = 5^3 = 125

Practice questions

4 questions

What is the value of $\displaystyle\sum_{k=0}^{5}\binom{5}{k}2^{5-k}$ ?

Select the correct answer:

$243$

$32$

$64$

$125$

+ 3 more questions

Part of

Counting

See all 9 lessons, what comes first, and what this unlocks.