CODEWITHSUNDEEP
pythonfunctionrecursion
Monika
Monika

Reputation: 301

Deriving a closed form from a recursive function

Given is the following recursively defined function, written in Python: 

def f(n, x, y):
    if n == 0:
        return (2*x)+(2*y)
    if n > 0 and y > x:
        return 0
    if n > 0 and x == 0 and y == 0:
        return 1
    if n > 0 and x > 0 and y == 0:
        return f(n-1, 0, f(n, x-1, y))
    else:
        return f(n-1, f(n, x-1, y-1), f(n, x-1, y))

I'm asked to find a closed form for f(1, x, y) when x >= y.

I found that the function returns 2^x whenever y = 0 or when x = y. I can't seem to be able to find a formula (or expand the one I already have) for any other case. Any help would be much appreciated.

Upvotes: 2

Views: 477

Answers (1)

JohanC
JohanC

Reputation: 80299

If you try to make a table forn==1 you get:

for x in range(10):
    for y in range(x+1):
        print(f"{f(1, x, y):6}", end='')
    print('')

Output:

     1
     2     2
     4     8     4
     8    24    24     8
    16    64    96    64    16
    32   160   320   320   160    32
    64   384   960  1280   960   384    64
   128   896  2688  4480  4480  2688   896   128
   256  2048  7168 14336 17920 14336  7168  2048   256
   512  4608 18432 43008 64512 64512 43008 18432  4608   512

This looks very much like Pascal's triangle, but with every row multiplied by 2x.

So, f(1, x, y) = 2**x * math.factorial(x) // (math.factorial(y) * math.factorial(x-y)).

Given the formula, it shouldn't be too difficult to prove via induction.

To simplify understanding function f, you can make a separate version for each n. As only n=0 and n=1 are considered in the question, just rewrite f given a fixed n:

def f0(x, y):
    return 2 * (x + y)

def f1(x, y):
    if y == 0:
        if x == 0:
            return 1
        else:
            return 2 * f1(x - 1, 0)
    elif y > x:
        return 0
    else:
        return 2 * (f1(x - 1, y - 1) + f1(x - 1, y))

It is clear that f1(x,0) = 2**x.

To prove the formula for f1(x,y) = 2**x * x! / (y! * (x-y)!), suppose it is already true for smaller x, then for 0 < y < x:

    f1(x,y) = 2 * (f1(x - 1, y - 1) + f1(x - 1, y))
or  f1(x,y) = 2 * (2**(x-1)*(x-1)! / ((y-1)! * (x-y)!)
                   + 2**(x-1)*(x-1)! / (y! * (x-y-1)!))
or  f1(x,y) = 2**x * (x-1)! * (1 / ((y-1)! * (x-y)!) + 1 / (y! * (x-y-1)!))
or  f1(x,y) = 2**x * (x-1)! * (y / (y! * (x-y)!) + (x-y) / (y! * (x-y)!))
or  f1(x,y) = 2**x * (x-1)! * (y+x-y ) / (y! * (x-y)!)
or  f1(x,y) = 2**x * x! / (y! * (x-y)!)

The case y=x needs to be considered separately. Here the calculation gives:

    f1(x,x) = 2 * (f1(x - 1, x - 1) + f1(x - 1, x))
or  f1(x,x) = 2 * (2**(x-1)*(x-1)! / ((x-1)! * (x-x)!) + 0)
or  f1(x,x) = 2**x
or  f1(x,x) = 2**x * x! / (x! * (x-x)!)      as in the formula

also, clearly f1(0,0) = 1 = 2**0 * 0! / ((0-0)! * 0!)

Upvotes: 3

Related Questions