<s>[INST] $k-$ Subsets of $\{1,\cdots,n\}$ with no consecutive integers This is a practice-exam question in discrete mathematics.
Denote this number (as described in the title) with $f(n,k)$ where $f(n,0)= 1$. I figured out that the recurrence $f(n+2,k) = f(n+1,k) + f(n,k-1)$ holds if $k \leq \left \lfloor \frac{n+1}{2}\right \rfloor$. Now I have to show that 
$$
\sum_{n=0}^\infty f(n,k)x^n = \frac{x^{2k-1}}{(1-x)^{k+1}}, \quad k\geq1
$$
Can I use induction on $k$ or is this straight-forward ?

I have now shown that $\sum_{k=0}^{\lfloor \frac{n+1}2 \rfloor} f(n,k) = f_n$. Does this help ?
 [/INST] OK, get at this with generating functions, à la Wilf's "generatingfunctionology", but in two indices. Define:
$$
F(x, y) = \sum_{n, k \ge 0} f(n, k) x^n y^k
$$
Write the recurrence as:
$$
f(n + 2, k + 1) = f(n + 1, k + 1) + f(n, k)
$$
Clearly $f(n, 0) = 1$ for all $n$, $f(0, k) = [k = 0]$, $f(1, k) = [0 \le k \le 1]$ (here $[\text[{condition}]$ is Iverson's convention, if the $\text{condition}$ is true, it is 1, else 0). We will need:
$$
\begin{align*}
\sum_{n \ge 0} f(n, 0) x^n &= \frac{1}{1 - x} \\
\sum_{k \ge 0} f(0, k) y^k &= 1 \\
\sum_{k \ge 0} f(1, k) x y^k &= x (1 + y)
\end{align*}
$$
Multiplying the recurrence by $x^n y^k$ and adding over $n, k \ge 0$ gives:
$$
\frac{F(x, y) - 1 - x (1 + y) - 1 / (1 - x) + 1 + x}{x^2 y}
  = \frac{F(x, y) - 1 - 1 / (1 - x) + 1}{x y} + F(x, y)
$$
The terms added in have been subtracted twice, and must be restored once. We get:
$$
\begin{align*}
F(x, y) &= \frac{1 + x y}{1 - x - x^2 y} \\
        &= \sum_{r \ge 0} x^r (1 + x y)^{r + 1} \\
        &= \sum_{r \ge 0} \sum_{s \ge 0} \binom{r + 1}{s} x^{r + s} y^s
\end{align*}
$$
The terms with $x^n y^k$ are those with $n = r + s$, $k = s$:
$$
f(n, k) = \binom{n - k + 1}{k}
$$
</s>