So I have a problem where I need to sum over a recursive function. The problem is that it is a 2 variables function and I can’t find any information on how to solve it. I know how to do it with 1 variable, but not with 2.
The problem: $$f(k,i)=f(k-1,i)+f(k-1,i-1)$$
I found a similar post with $f(k,i)=f(k-1,i)+f(k,i-1)$ but couldn’t understand how to convert the answer to my problem.
Base cases: $$f(k,0)=1\text{ for every }k,$$ $$f(0,i)=1\text{ for every }i.$$
Here's a table of the values of $\ f(k,i)\ $ for $\ 0\le k\le9\ $ and $\ 0\le i\le5\ $. By inspection, you can guess that $\ f(k,i)=2^k\ $ for $\ 0\le k\le i\ $, and this is easy enough to prove by induction. $$ \begin{array}{c|ccc } i\\ \hline 5&1&2&4&8&16&32&63&120&219&382\\ 4&1&2&4&8&16&31&57&99&163&256\\ 3&1&2&4&8&15&26&42&64&93&130\\ 2&1&2&4&7&11&16&22&29&37&46\\ 1&1&2&3&4&5&6&7&8&9&10\\ 0&1&1&1&1&1&1&1&1&1&1\\ \hline k&0&1&2&3&4&5&6&7&8&9 \end{array}$$ Note that the numbers along any diagonal to the right of the main diagonal, $\ k=i\ $, are the sums of the numbers up the diagonal immediately to its left: $$ f(k,k-a)=\sum_{r=a+1}^kf(r,r-a-1) $$ for $\ k>a>0\ $. Using this observation, I'm guessing that a general formula for the numbers to the right of the main diagonal is $$ f(k,i)=2^k-\sum_{j=0}^{k-i-1}{k\choose j} $$ for $\ k>i\ge0\ $. I've checked that the formula is correct for all the numbers in the above table, so I'm pretty sure that it will hold in general. I haven't bothered trying to prove it, but I expect that it should be fairly straightforward to do by induction. I doubt that there's any simpler expression for the sums, $\ \sum_\limits{j=0}^{k-i-1}{k\choose j}\ $, of binomial coefficients.
