One can go over all subsets of the set $\{1,...,n\}$ by using a binary representation - $0$ at index $i$ means that element $i$ is not in the set, while $1$ at index $i$ meanas that it is.
Furthermore, one can count the number of subsets that have no adjacent elements (ie, if $i$ is in the subset then $i-1,i+1$ are not) by counting binary vectors of length $n$ with no adjacent $1$s, recursively: denote by $a_n$ the number of such binary vectors. Either element $1$ is not in the subset (ie, at index $1$ in the binary vector there is a $0$) and there are $a_{n-1}$ ways to continue, or there is $10$ at indexes $1,2$ in the binary vector and there are $a_{n-2}$ ways to continue. Meaning, the number of such binary vectors (subsets) is $a_n = a_{n-1} + a_{n-2}$.
However, how can we count the number of subsets of some fixed size $0 \leq k \leq n$ that have no adjacent elements? Somehow, we need to calculate the number of substrings of length $k$ of binary strings of length $n$ that have no adjacent $1$'s. The number of subsets of length $k$ of the main set is $\binom{n}{k}$.
I would appreciate some guidance.
Try to think about subset of set {1,2, ..., n-k+1}. Standard method of counting in combinatorics is finding bijection beetwen some sets.
Below is my solution.
It will be ${n - k + 1 \choose k}$. For every subset of set {1, 2, ..., n-k,n-k+1} try to add 0 to smallest element, 1 to next element, ..., $k-1$ to largest element. You will get subset of size $k$ with no adjacent elements. Conversly if from set with no adjacent elements you will subtract $k-1$ from largest element, $k-2$ from second largest element, ..., $0$ from smallest number you will get some subset of set {1, 2, ..., n-k+1} - so given function is bijection.