Proof by induction using factorials

Question

Prove by induction that:

There are exactly $n-k+1\choose{k}$ choices for choosing k numbers from the set {1,,,,n} with no two numbers adjacent.

I have no idea :( I thought I would start with base case n=1, k=1 then assume true for n but then not at all sure for last step.

Answer 1

Not what you seem to be looking for, but...

Call your numbers $1 \le a_1 < a_2 < \ldots < a_k \le n$, and define auxiliary variables $x_0$ through $x_k$, where:

$\begin{align} 1 + x_0 &= a_1 \\ a_1 + x_1 + 2 &= a_2 \\ &\ldots \\ a_{k - 1} + x_{k - 1} + 2 &= a_k \\ a_k + x_k &= n \end{align}$

Note that for all $i$ we have $x_i \ge 0$, and furthermore by adding up all equations:

$\begin{align} x_0 + x_1 + \dotsb + x_k + 2 k - 1 = n \end{align}$

So you are all set up, by the typical stars-and-bars argument this has

$$ \binom{(n - 2 k + 1) + (k + 1) - 1}{(k + 1) - 1} = \binom{n - k + 1}{k} $$

solutions.

Added later: For stars-and-bars here, if you have $x_1 + \dotsb + x_k = n$, imagine you have $n$ stars ($*$) to be distributed among $k$ buckets (the $x_i$), separated by $k - 1$ bars ($|$). This is string of $n + k$ places in all, and $k - 1$ of those are to be taken by the bars. Thus

$$\binom{n + k - 1}{k - 1}$$

possibilities in all.

Answer 2

Here is a combinatorial proof of the formula:

Place $n - k$ red balls in a row. This creates $n - k + 1$ gaps, consisting of $n - k - 1$ gaps between successive balls and the two ends of the row. If $k \leq n - k + 1$, we can select $k$ of these $n - k + 1$ gaps in which to place $k$ blue balls. We can now number the balls from left to right. Therefore, there are $$\binom{n - k + 1}{k}$$ ways to select $k$ numbers from the set $\{1, 2, \ldots, n\}$ so that no two consecutive numbers are adjacent.

Answer 3

I prefer a combinatorial explanation, but you can prove it by a double induction as follows. For $k\ge 1$ let $P(k)$ be the statement that the set $[n]=\{1,\ldots,n\}$ has $\binom{n-k+1}k$ acceptable $k$-subsets for each $n\ge 1$. This is clearly true for $k=1$, since $\binom{n-1+1}1=n$, and every $1$-element subset of $[n]$ is acceptable.

Now suppose that $k>1$, and that $P(\ell)$ is true for $1\le\ell<k$; we’ll prove $P(k)$ by induction on $n$. That is, we’ll prove by induction on $n$ that $[n]$ has $\binom{n-k+1}k$ acceptable $k$-subsets for each $n\ge 1$.

This is certainly true for $n=1$: $\binom{n-k+1}k=\binom{-k}k=0$, and $\{1\}$ certainly has no acceptable $k$-element subset when $k>1$.

For the induction step let $n>1$, and assume as induction hypothesis that $[m]$ has $\binom{m-k+1}k$ acceptable $k$-subsets for $1\le m<n$. We want to show that $[n]$ has $\binom{n-k+1}k$ acceptable $k$-subsets.

We’ll split the acceptable $k$-subsets of $[n]$ into two types, those that contain the number $n$ and those that do not. It’s easier to count the second type, so I’ll start with it.

• $A$ is an acceptable $k$-subset of $[n]$ that does not contain $n$ if and only if $A$ is an acceptable $k$-subset of $[n-1]$; by the induction hypothesis on $n$ there are $\binom{(n-1)-k+1}k=\binom{n-k}k$ such sets.

• $A$ is an acceptable $k$-subset of $[n]$ that contains $n$ if and only if $A\setminus\{n\}$ is an acceptable $(k-1)$-subset of $[n-1]$ that does not contain the number $n-1$, i.e., if and only if $A\setminus\{n\}$ is an acceptable $(k-1)$-subset of $[n-2]$. By the induction hypothesis on $k$ there are $\binom{(n-2)-(k-1)+1}{k-1}=\binom{n-k}{k-1}$ such sets.

Thus, the total number of acceptable $k$-subsets of $[n]$ is

$$\binom{n-k}k+\binom{n-k}{k-1}=\binom{n-k+1}k$$

by Pascal’s identity. It follows that $[n]$ has $\binom{n-k+1}k$ acceptable $k$-subsets for all $n\ge 1$, i.e., that $P(k)$ is true. This completes the induction step of the induction on $k$, and we can therefore conclude that $P(k)$ is true for all $k\ge 1$.