# What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a

I'm given the following python function:

def recurser(i, j):
x = 0
if j == 0:
return 1
if i == 0:
return 1
x += recurser(i, j - 1)
x += recurser(i - 1, j)
x += 1
return x


And I'm Asked to find x for any i = j = n where n can be any positive integer. however the recursion can do the job but the question says no recursion is allowed so that I have to solve the following recursive function:

• F(n,n) = F(n-1,n) + F(n, n-1) + 1
• F(0,a) = 1 for every positive a
• F(a, 0) = 1 for every positive a

Is there any solution for it?

Your function produces the sequence A109128, that is $$\mathit{recurser}(i,j) = 2\binom{i+j}{i} - 1.$$ You can prove this by induction.