Combinatorial argument for solution of recursion behaving similarly as Pascals triangle?

Question

Given the following recursion:

$$ F(n,d) = F(n-1,d) + F(n-1,d-1) + 1 $$

With initial conditions $F(0,d)=1,F(n,1)=1$ and $n\in\mathbb N_0, d\in\mathbb N$.

I noticed that it holds (By writing out the table for $n,d$ and doing some tweaking):

$$ F(n,d)=2\sum_{k=1}^{d-1}\binom{n}{k}+1$$

Can this solution be justified (proven) by a combinatorial argument?

I want to avoid proving it by solving the above recursion in two vairables.

The recursion seems similar to the one for diagonals in Pascals triangle.

Answer 1

Let $G(n,d)=\frac{F(n,d)+1}{2}$. Then $G$ is given by the recurrence $$G(n,d) = G(n-1,d) + G(n-1,d-1)$$ with initial conditions $G(0,d)=1$ and $G(n,1)=1$. We will show that $$H(n,d)=\sum_{k=0}^{d-1}\binom{n}{k}$$ satisfies the same recurrence and so is equal to $G(n,d)$, from which your identity for $F$ follows easily. The initial conditions are trivial to verify.

Combinatorially, $H(n,d)$ counts the number of subsets of $\{1,\dots,n\}$ with fewer than $d$ elements. Such a subset either contains $n$ as an element or doesn't. The subsets that do contain $n$ are in bijection with the subsets of $\{1,\dots,n-1\}$ with fewer than $d-1$ elements (by removing $n$) and the subsets that do not contain $n$ are in bijection with the subsets of $\{1,\dots,n-1\}$ with fewer than $d$ elements. That is, $$H(n,d)=H(n-1,d-1)+H(n,d-1),$$ as desired.

Answer 2

I have a proof by induction, but not a combinatorial proof. The function trivially holds for the base cases. Let the function be assumed to hold for $F(n-1, d)$ and $F(n-1, d-1)$. Then we want to show that it also holds for $F(n, d)$. Basically, $$2\sum_{k=1}^{d-1}\binom{n}{k}+1 = \left(2\sum_{k=1}^{d-1}\binom{n-1}{k}+1\right) + \left(2\sum_{k=1}^{d-2}\binom{n-1}{k}+1\right) + 1$$ has to be shown to be true.

Rearranging a bit yields $$\sum_{k=1}^{d-1}\binom{n}{k} = 2\sum_{k=1}^{d-2}\binom{n-1}{k} + \binom{n-1}{d-1} + 1 \tag 1$$

By Pascal's rule, the LHS of $(1)$ can be made into $$\sum_{k=1}^{d-1} \left( \binom{n-1}{k} + \binom{n-1}{k-1} \right) = \sum_{k=1}^{d-1} \binom{n-1}{k} + \sum_{k=0}^{d-2} \binom{n-1}{k} $$

Grouping from $k = 1$ to $k = d-2$ yields that the LHS of $(1)$ is $$2\sum_{k=1}^{d-2}\binom{n-1}{k} + \binom{n-1}{d-1} + \binom{n-1}{0}$$

Since $\binom{n-1}{0} = 1$, the LHS of $(1)$ simplifies to $$2\sum_{k=1}^{d-2}\binom{n-1}{k} + \binom{n-1}{d-1} + 1$$, which is exactly equal to the RHS. Therefore, $$F(n,d)=2\sum_{k=1}^{d-1}\binom{n}{k}+1$$ is proved by induction.