How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?

Solution 1:

Another good way of solving problems like this is to set up a correspondence with a problem you already know how to solve. In this case, imagine that you've got a sorted set of six non-consecutive numbers $a_1, a_2, \dots a_6$ between 1 and 49. What does it look like? Well, the first number $a_1$ is essentially arbitrary; it can't be greater than a certain value (i.e. 39) or else there isn't 'room' for five more non-consecutive numbers above it, but we can ignore that for now. The second number $a_2$ has to be greater than $a_1+1$ — that's what it means to be nonconsecutive, after all — so we know that $a_2-1$ (call this $b_2$) is greater than $a_1$. Similarly, $a_3$ has to be greater than $a_2+1$, so $a_3-1$ is greater than $a_2$, and $a_3-2$ is greater than $a_2-1 = b_2$; we can call this $b_3$. And so on, and so forth, until we define $b_6 = a_6-5$. But this correspondence works both ways — given the $b_n$ it's easy to get the $a_n$ — and so we have a one-to-one correspondence between our non-consecutive sets of numbers and an ordinary combination (but with a different upper bound - can you see what it should be?). It takes a while to build this sort of instinct, but learning how to spot these correspondences is the most basic tool for proving most combinatorial identities.

Solution 2:

In analogy to the Pascal triangle, define D(n,r) as the number of ways to select r items from n with no two consecutive. You can either use 1 or not. If you do use it, you can't use 2 but only need to pick r-1. If you don't use it you have n-1 items to pick r from. So D(n,r)=D(n-2,r-1)+D(n-1,r). The base case is D(2r-1,r)=1For values like this you can use a spreadsheet.