# Generating function of sequence depending on another sequence

Let $$a(n,k) = |$${$$A ⊂ [n]: |A| = k, A$$ does not contain two consecutive elements$$}|$$
Prove that $$a(n,k) = a(n−1,k)+a(n−2,k −1)$$ for $$k ≥ 2$$
and use it to compute the generating function $$A_k(x) = \sum_{n \geq 1} a(n,k)x^n$$

then use that generating function to prove that $$\sum_{k \geq 0} \binom{n-k+1}{k} = F_{n+2}$$ where $$F_{n+2}$$ is the n+2th term of the Fibonacci sequence.

To get the generating function, I wrote $$\sum_{n \geq 1} a(n-1,k)x^n = xA_k(x)$$ and $$\sum_{n \geq 1} a(n-2,k-1)x^n = x^2A_{k-1}(x)$$ then I get $$A_k(x) = xA_k(x) + x^2A_{k-1}(x)$$

however I cannot find a way to write $$A_{k-1}(x)$$ in terms of $$A_k(x)$$, so I do not know how to solve the equation to get the generating function. The only thing I came up with is to write $$A_{k-1}(x)=xA_{k-1}(x)+x^2A_{k-2}(x)$$ which just leads to the same problem (what is $$A_{k-2}(x)$$ in terms of either $$A_k(x)$$ or $$A_{k-1}(x)$$)

EDIT: I solved the first part, see below

• A subset of $[n]$ of size $k$ with no two consecutive elements either does not have $n$ as an element and therefore is a subset of $[n-1]$ of size $k$ with no two consecutive elements... or does have $n$ as an element and so can be described as a subset of $[n-2]$ of size $k-1$ unioned with $\{n\}$ (noting that $n-1$ is adjacent to $n$ and so could not have been in the other $k-1$ elements) Commented Apr 8 at 14:50
• This part I understand, what I'm having trouble with is the generating function part. But thanks, I will add this to the post. Commented Apr 8 at 15:30

Consider $$A_2$$: $$a(n,1) = n$$ for all $$n$$ since it's $$n$$ sets, each with a single element. Therefore, $$a(n,2)=a(n-1,2)+(n-2)$$
The generating function for $$A_2$$ is $$\frac{x^2}{(1-x)^3}$$ which we can get by differentiating the geometric series twice, dividing by 2 and multiplying by $$x^2$$ since $$a(1,2)=a(2,2)=0$$
Since $$\sum_{n\geq1}a(n-1,k) = \sum_{n\geq0}a(n,k) = xA_k(x)$$ and similarly $$\sum_{n\geq1}a(n-2,k-1) = x^2A_{k-1}(x)$$ we get
$$A_k(x)=xA_k(x)+x^2A_{k-1}(x)$$ so $$A_k(x)=\frac{x^2}{1-x}A_{k-1}(x)$$ and knowing the value of $$A_2(x)$$ a general formula for $$A_k(x)$$ can be obtained
so $$A_k(x)=(\frac{x^2}{1-x})^{k-2}A_2(x)=\frac{x^{2k-2}}{(1-x)^{k+1}}$$