1
$\begingroup$

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.

$\endgroup$

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.