Change the Recursive Relation into Formula : $f(n,k) = f(n-1,k) + f(n-2, k-1)$

Question

I am trying to find the formula for the number $f(n,k)$ which is defined as the number of $k$-subsets of $[n]$ in which no two elements are consecutive numbers in $[n]$.

From the simple thinking I had made up following recursion:

$$f(n,k) = f(n-1,k) + f(n-2, k-1) $$

This is true since I can construct without last element of $[n]$ then make up $k$-subsets, then otherwise must contain the last element of $[n]$ then construct remaining $k-1$ elements among $[n-2]$ since with the last one, I can't use $n-1$.

However, I had never learned any techniques regarding changing those recursion into a well-summarized formula in terms of $n$ and $k$.

Any guidance would be appreciate.

Answer 1

$$ f(n,k)=f(n-1,k)+f(n-2,k-1) \\ f(n-1,k)=f(n-2,k)+f(n-3,k-1) \\ f(n-2,k)=f(n-3,k)+f(n-4,k-1) \\ ... \\ f(2,k)=f(1,k)+f(0,k-1) $$ We sum all expressions : $$ f(n,k)+\sum_{p=2}^{n-1} f(p,k) = f(1,k)+\sum_{p=2}^{n-1}f(p,k) + \sum_{p=0}^{n-2} f(p,k-1) $$ We can cancel 2 sumes : $$ f(n,k) = f(1,k)+ \sum_{p=0}^{n-2} f(p,k-1) $$ This can help a little bit ? Daniel

Answer 2

We apply generating functions. Let $f(n,k) = a_{n,k}$ and let $F = \sum_{n,k \geq 0} a_{n,k} x^n y^k$. We have the reccurence $a_{n + 2, k + 1} = a_{n + 1, k + 1} + a_{n,k}$ for all $n,k \geq 0$ (we take $a_{n,k} = 0$ for $k > n$). Multiplying by $x^n y^k$ and summing we get \begin{align} \sum_{n \geq 0} \sum_{k \geq 0}a_{n + 2,k+1}x^ny^k = \sum_{n \geq 0} \sum_{k \geq 0}a_{n+1,k+1}x^ny^k+F \end{align} We simplify the right sum first. Note that $a_{n,0} = 1$. We have \begin{align} \sum_{n \geq 0} \sum_{k \geq 0}a_{n + 1,k + 1} x^n y^k &= \frac{1}{xy}\sum_{n \geq 1} \sum_{k \geq 1} a_{n,k} x^n y^k\\ &= \frac{1}{xy} \bigg(\sum_{n \geq 1} \sum_{k \geq 0} a_{n,k} x^ny^k-\sum_{n \geq 1}a_{n,0}x^n\bigg)\\ &= \frac{1}{xy} \bigg(\sum_{n \geq 1} \sum_{k \geq 0} a_{n,k} x^ny^k - \frac{x}{1- x} \bigg)\\ &= \frac{1}{xy} \bigg(F-\sum_{k \geq 0}a_{0,k} y^k - \frac{x}{1-x}\bigg)\\ &= \frac{1}{xy} (F - 1 - \frac{x}{1-x}) \end{align} For the right hand sum we get \begin{align} \sum_{n \geq 0} \sum_{k \geq 0}a_{n + 1,k + 1} x^ny^k &= \frac{1}{x^2y}\sum_{n \geq 2} \sum_{k \geq 1} x^n y^k\\ &= \frac{1}{x^2y} \bigg(\sum_{n \geq 1} \sum_{k \geq 1}x^n y^k - \sum_{k \geq 1} a_{1,k}xy^k\bigg)\\ &= \frac{1}{x^2y}\bigg(\sum_{n \geq 1} \sum_{k \geq 1}x^n y^k - xy\bigg)\\ &= \frac{1}{x^2y}\bigg(F - 1 - \frac{x}{1-x} - xy\bigg) \end{align} Putting this all together we get \begin{align} \frac{1}{x^2y}\bigg(F - 1 - \frac{x}{1-x} - xy\bigg) = F + \frac{1}{xy} (F - 1 - \frac{x}{1-x}) \end{align} Isolating for $F$ we get \begin{align} F = \frac{1 + xy}{1 - x(1 + xy)} = \frac{1}{x} \frac{x(1 + xy)}{1 - x(1 + xy)} \end{align} Using the geometric series formula and the convention $\binom{n}{k} = 0$ for $k > n$ we get \begin{align} F &= \frac{1}{x}\sum_{n \geq 1} x^n(1 + xy)^n\\ &= \frac{1}{x}\sum_{n \geq 1} x^n \sum_{k = 0}^n \binom{n}{k} x^k y^k\\ &= \frac{1}{x}\sum_{n \geq 1} \sum_{k \geq 0} \binom{n}{k} x^{n + k}y^k\\ &= \frac{1}{x}\sum_{k \geq 0} \sum_{n \geq 1} \binom{n}{k} x^{n + k}y^k\\ &= \frac{1}{x}\sum_{k \geq 0} \sum_{n \geq k} \binom{n - k + 1}{k} y^k x^{n + 1}\\ &= \sum_{k \geq 0} \sum_{n \geq k} \binom{n - k + 1}{k} x^n y^k\\ &= \sum_{n,k \geq 0} \binom{n - k + 1}{k} x^n y^k \end{align} the last step follows since the binomial coefficient is zero when $n < k$. Therefore $f(n,k) = a_{n,k} = \binom{n - k + 1}{k}$.

Answer 3

Just looking at some values and arranging them in a grid (the left column corresponds to $n=0$ and the top row corresponds to $k=0$)

1   1   1   1   1   1   1   1   1   1
0   1   2   3   4   5   6   7   8   9
0   0   0   1   3   6  10  15  21  28
0   0   0   0   0   1   4  10  20  35
0   0   0   0   0   0   0   1   5  15
0   0   0   0   0   0   0   0   0   1

This looks a bit like a skew version of Pascal's triangle:

                1
             1     1
          1     2     1
       1     3     3     1
    1     4     6     4     1
 1     5    10    10     5     1

etc. It's well known that the elements of Pascal's triangle are given by $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

A little manipulation of indices then shows us that the table above can be computed as:

$$ f(n,k) = \binom{n-k+1}{k} = \frac{(n-k+1)!}{k!(n-2k+1)!} $$

A straightforward induction proof can then prove this for all $n$ and $k$.