-2

I have come across a recurrence relation i.e

$$f(a,b) = f(a-1,b) + f(a-1,b-1)$$ and the base case is $f(x,0) = 2$ for any positive $x$ and $f(x,y) = 0$ if $x \leq y$. Note that $a$ and $b$ are positive.

Can anyone please tell me if we can derive a formula for this equation using some relation between $a$ and $b$?

Nash J.
  • 1,235
  • 8
  • 18
Nikhil Agrawal
  • 23

1 Answers1

0

Plase take a look at the Pascal's Triangle. If you try and calculate some values, you should see that your recurrence is very simmilar up to a factor 2, at least for $b\geq 0$. So the result ist $f(a,b) = 2 {a \choose b}$.

denklo
  • 781