0

I have the following relation:

$$F(x, y) = F(x, y - 1) + F(x - 1, y - 1)$$

and the initial conditions: $F(x, 1) = 1$ and $F(1, y) = y$.

How can I solve this recurrence?

Thank you in advance!

DMcMor
  • 9,407
Alexander V.
  • 1
  • You should so your attempts first.See this :https://math.meta.stackexchange.com/questions/9959/how-to-ask-a-good-question and this : https://math.meta.stackexchange.com/questions/1803/how-to-ask-a-homework-question – Jaideep Khare Apr 09 '17 at 19:40
  • You should calculate a table of values. Try to find patterns within the table or perhaps you will recognize the numbers you are seeing. Hint: This is actually a fairly well-known recurrence, unless I am gravely mistaken. – Will Craig Apr 09 '17 at 19:59
  • Something fishy here. $F(0,2)=F(0,1)+F(-1,1)=2$ and $F(1,2)=F(1,1)+F(0,1)=2$ so $F(1,3)=F(1,2)+F(0,2)=4$ but $F(1,3)=3$ according to initial conditions. – Jens Apr 09 '17 at 20:56
  • https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula – DanielV Apr 09 '17 at 23:35
  • @DanielV: Doesn't this require that $x>0$? – Jens Apr 09 '17 at 23:39

1 Answers1

0

I have programmed the recursive relation and obtained the result below, the blue lines indicating the "computation flow", for example on North-West corner: $46 = 9 + 37$.

You should be able, from this table, to elaborate conjectures (for example about powers of 2 that you can see on and below line with equation $y=x+1$).

enter image description here

Jean Marie
  • 81,803