Choose 'k' numbers from 'n' with no two consecutive.

Proof 1: Using stars and bars
There are 'n' positions(1,2....n) laid down in a line from which we have to pick 'k' positions such that no 2 are adjacent.
Let's say the picked positions are X and unpicked are O.
First we put 'k' Xs followed by 'n-k' Os. (So total positions are 'n').
Now the picked positions can't be adjacent so we put 'k-1' Os between them.
Now we are left with how many Os? n-k-(k-1) = n-2k + 1
These remaining Os can be freely distributed among the 'k+1' buckets.
Why 'k+1' buckets?
Because 'k' Xs have 1 gap on either side and 'k-1' gaps between them. So total k-1+2 = k+1 gaps(buckets).
So we have 'n-2k+1' identical objects(remaining Os) to be put in 'k+1' distinct buckets.
Stars and bars formula for the same for 'n' identical objects and 'k' distinct buckets:
(n+k-1)C(k-1)
Putting the new values here:
( (n-2k+1) + (k+1) - 1)C((k+1) - 1)
=
(n-k+1)C(k) => H.P.



Proof 2:(Compression trick)
 

Picture the numbers as spots on a line

Write the numbers 1, 2, 3 … n in a row.
Your job is to place k check-marks on some of those spots, but no two check-marks are allowed to sit next to each other (that’s the “no consecutive numbers” rule).

---

The trick: squeeze the gaps away

1. Label the chosen numbers
   Call them

   $$a_1 < a_2 < \dots < a_k .$$

   Because you never picked two in a row, each gap between $a_i$ and $a_{i+1}$ is at least 1.

2. Shift each choice left by its position in the list
   Define

   $$b_1 = a_1,\quad b_2 = a_2 - 1,\quad b_3 = a_3 - 2,\; \dots\; ,\quad b_k = a_k - (k-1).$$

   In words: for the 2nd chosen number slide it left one step, for the 3rd slide it left two steps, and so on.

3. What just happened?

   • Because each gap was at least one, sliding never makes two numbers collide.

   • After sliding, the $b_i$’s are still in increasing order but can now sit next to each other—we erased the “no-consecutive” rule!

   • The smallest $b_1$ is still at least 1.

   • The largest $b_k$ can’t go past $n-k+1$ (we slid $a_k$ left by $k-1$).

   So the list

   $$b_1 < b_2 < \dots < b_k$$

   is simply any set of k distinct numbers chosen from

   $$\{1,2,3,\dots,n-k+1\}.$$

4. Reverse the shift = perfect one-to-one match
   Starting with any $k$ numbers inside $\{1,\dots,n-k+1\}$ and sliding them right (add $0,1,2,\dots,k-1$) recreates a legal gap-filled set in $\{1,\dots,n\}$.
   Therefore the two tasks are in bijection (perfect pairing).

---

Count the easy task

Choosing $k$ numbers from a list of $n-k+1$ without any restrictions is the ordinary binomial coefficient

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

Because of the perfect match above, that is also the number of gap-separated (no-consecutive) choices you wanted.

---

Quick example

Take $n=8,\;k=3$.

legal picks (no two consecutive)	slide left (subtract 0,1,2)	lands in $\{1,\dots,6\}$
$\{1,3,6\}$	$\{1,2,4\}$	✓
$\{2,5,8\}$	$\{2,4,6\}$	✓
$\{3,5,7\}$	$\{3,4,5\}$	✓

All $\binom{6}{3}=20$ “easy” triples in $\{1,…,6\}$ correspond to 20 legal triples in $\{1,…,8\}$.