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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.