You may also like

problem icon

Telescoping Series

Find $S_r = 1^r + 2^r + 3^r + ... + n^r$ where r is any fixed positive integer in terms of $S_1, S_2, ... S_{r-1}$.

problem icon

The Kth Sum of N Numbers

Yatir from Israel describes his method for summing a series of triangle numbers.

problem icon

The Harmonic Triangle and Pascal's Triangle

The harmonic triangle is built from fractions with unit numerators using a rule very similar to Pascal's triangle.

Binomial Coefficients

Stage: 4 and 5
Article by Ben Millwood

When trying to work out the number of ways of choosing things, you'll first need to come up with a good way of keeping track of what choices you've found already.

You could write T for each thing you took and L for each thing you left, and represent choosing 2 from 5 as TTLLL, TLTLL, TLLTL, ...

You could decide you were choosing from the first $n$ natural numbers, and represent choosing 2 from 5 as {1,2}, {1,3}, {1,4}, ...

You should decide which representation feels most natural to you. Which is the most useful may depend on the problem you're trying to solve at the time, so try both.

To be sure you have all the choices, look for patterns. Ask yourself, do I have all the choices where I take the first thing? What about all the choices where I don't take the first thing?

When you're trying to prove that ${n \choose k} = {n \choose n-k}$, consider why ${3 \choose 1}$ turned out to be the same as ${3 \choose 2}$. What would be a fast way to choose 99 elements from 100?

For the addition rule, I think the TLTLL representation is more useful than the {1,3} representation. How many choices begin with T? How many begin with L?

For the first extension, one approach is to just apply the addition rule repeatedly. If you had a choices interpretation of the addition rule, think about what that means here. This time the {1,3} representation is probably more useful.

For the second extension, consider what the left-hand side means in terms of choices, or try a proof by induction, or try using the binomial formula.

For the third extension, we're trying to write a choice from $2n$ things in terms of choices from $n$ things. How could you choose from $2n$ things by making choices from sets of $n$ things? Alternatively, try using the binomial formula: see also Binomial.

These extensions are meant to be very hard, so don't lose sleep over them.