Followers 0

# Recursion

## 3 posts in this topic

Posted · Report post

Find a closed-form expression for F(a,b) where:

F(a,b) = F(a-1,b) + F(a-1,b-1),

F(a,0) = 1 for all a

F(0,b) = 0 for all b

a and b are positive integers

0

##### Share on other sites

Posted (edited) · Report post

What does F(0,0) evaluate to? you need it for F(1,1)

In case F(0,0)=1 then F(a,b) = b choose a, as in the binomial coefficient between b and a.

In case F(0,0)=0 then it's the binomial coefficient between b-1 and a.

Given F(0,0) there is only one solution, you can see this if you draw an xy axis and mark a on the x axis and b on the y axis, then mark 0's on the a axis and 1's on the b axis, then the value of every other point on the plane is the sum of values of the point to it's left and the point under that...

Edited by Anza Power
0

##### Share on other sites

Posted · Report post

What does F(0,0) evaluate to? you need it for F(1,1)

In case F(0,0)=1 then F(a,b) = b choose a, as in the binomial coefficient between b and a.

In case F(0,0)=0 then it's the binomial coefficient between b-1 and a.

Given F(0,0) there is only one solution, you can see this if you draw an xy axis and mark a on the x axis and b on the y axis, then mark 0's on the a axis and 1's on the b axis, then the value of every other point on the plane is the sum of values of the point to it's left and the point under that...

F(0,0) = 1

Sorry for leaving that out.

Nice work, you are correct!

0

## Create an account

Register a new account