Choosing numbers without consecutive numbers.

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$,

In a way where we have no consecutive numbers in the set? (like $1,2$)

Assuming that the order of choice doesn’t matter, imagine marking the positions of the $r$ chosen numbers and leaving blank spaces before, between, and after them for the $n-r$ non-chosen numbers; if $r=3$, for instance, you’d get a skeleton like $_|_|_|_$, where the vertical bars represent the positions in $1,2,\ldots,n$ of the chosen numbers. The remaining $n-r$ numbers must go into the $r+1$ open slots in the diagram, and there must be at least one of them in each of the $r-1$ slots in the middle. After placing one number in each of those slots, we have $n-r-(r-1)=n-2r+1$ numbers left to place arbitrarily in the $r+1$ slots. This is a standard stars-and-bars problem: there are

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

ways to do it. The reasoning behind the formula is reasonably clearly explained at the link.

Let $g(n,r)$ be the answer to the OP's question.

There is a simple recursion that $g$ satisfies.

$\tag 1 g(n+1,r) = g(n,r) + g(n-1,r-1)$

To see this consider the set $\{1,2,3,\dots,n,n+1\}$. We can partition the solution set (subsets with $r$ elements) into those that contain the number $n+1$, call it $\mathcal N$, and those that don't, call it $O$.

If $A \in \mathcal N$ then $n \notin A$ and clearly $|\mathcal N| = g(n-1,r-1)$.

If $A \in \mathcal O$ then $n+1 \notin A$ and clearly $|\mathcal O| = g(n,r)$.

The total sum is the sum of the blocks, giving us $\text{(1)}$.

The function $g$ satisfies boundary conditions and without finding a closed formula for $g$ we can still use a computer program to calculate $g(n,r)$ - see the next section.

There are many paths you can take if you work on finding a closed formula for $g$. No doubt, you will eventually find that

$\tag 2 g(n,r) = \binom{n+1-r}{r}$

When you plug this into $\text{(1)}$ you will see Pascal's rule on your scrap paper.

Python program (using a recursive function)

def daH(x:int,y:int):        # g(x,y)=g(x-1,y)+g(x−2,y−1)
    if y == 1:               # on wedge boundary output known
        return x
    if x == 2 * y - 1:       # on wedge boundary output known
        return 1
    r = daH(x-1,y) + daH(x-2,y-1)
    return r


print('g(7,4)  =', daH(7,4))
print('g(10,4) =', daH(10,4))

OUTPUT: