$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 ?
 A: I think your recurrence should hold for all $k$- why wouldn't it? Then you have induction on $k$, as you suggested: Let the sum equal $F_k(x)$, and (Assume $k \geq 2$):
\begin{align*} F_k(x) = \sum_{n = 0}^{\infty}f(n,k)x^k &= f(0,k) + f(1,k)x + \sum_{n = 2}^{\infty}f(n-1,k)x^n + \sum_{n = 2}^{\infty}f(n - 2,k - 1)x^n \\
&=0 + 0x + \sum_{n = 1}^{\infty}f(n,k)x^{n+1} + \sum_{n = 0}^{\infty}f(n,k-1)x^{n+2} \\
&=xF_k(x) + x^2F_{k-1}(x)\end{align*}
And so:
$$F_k(x) = \frac{x^2}{1 - x}F_{k-1}(x)$$
Now you are done if you can establish the base case. We can actually make this easier by realizing that the inductive step works if $k = 1$, except we can't remove $f(1,k)x = f(1,1)x = x$. We get:
$$F_1(x) = x + xF_1(x) + x^2F_0(x)$$
Now, since $f(n,0) = 1$:
$$F_0(x) = \sum_{n = 0}^{\infty}x^n = \frac{1}{1 - x}$$
Now you can easily see that:
$$F_1(x) = \frac{x}{(1 - x)^2}$$
(So I think your numerator should be $x^{2k - 1}$)
A: 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}
$$
