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

  • $\begingroup$ 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) $\endgroup$
    – JMoravitz
    Commented Apr 8 at 14:50
  • $\begingroup$ This part I understand, what I'm having trouble with is the generating function part. But thanks, I will add this to the post. $\endgroup$ Commented Apr 8 at 15:30

1 Answer 1


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}}$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .