1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

How I found out: I computed the first few values, and searched the OEIS.

$\endgroup$
1
  • $\begingroup$ thanks a lot. the proof would be by induction as you said. in the middle of the proof you could use the pascal's rule. $\endgroup$ – ashkan khademian Oct 25 '20 at 14:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.