1

I want to know how to approach this two dimensional recurrence relation and how can a generating function be generated for this recurrence.

$$F(N,K) = F(N-1,K) + F(N-1,K-1) + F(N-2,K-1)\text{ with }N>0,K>0.with,$$

$$F(N,0) = 1,$$ $$F(N,1) = 2*N,$$ $$F(N,K) = 2 , when N=K $$

for Example :- We very well know that

$$F(N,K) = F(N-1,K) + F(N-1,K-1)$$

is nothing but simply

$$F(N,K) = NCK$$

George
  • 23

1 Answers1

1

OK. Let me take a shot at the "approach" part. I'm using MathJax for Brevity. $$F_{n,k}=F_{n-1,k} + F_{n-1,k-1}$$ $$=>F_{n-1,k}=F_{n-2,k} + F_{n-2,k-1}$$ $$Adding => F_{n,k} + F_{n-1,k}= F_{n-1,k} + F_{n-1,k-1} + F_{n-2,k} + F_{n-2,k-1}$$ $$=>F_{n,k}= F_{n-1,k-1} + F_{n-2,k} + F_{n-2,k-1} --> (1)$$ Which is similar to your recurrence but is not the same. For the first recurrence the solution is $$F_{n,k} = {n \choose k}$$ So "one" of the solution to the recurrence (1) is $$F_{n,k} = {n \choose k} + {n-1 \choose k}$$ the other solution is simply $n \choose k$ since we simply just did $F_{n,k}+F_{n-1,k}$. The approach that I'm suggesting is to find out if any such algebraic manipulation of the recurrences result finally in your recurrence. I did try this out a bit and it does seem to be kind of hard to find the solution... Now, I know from past that there are other recurrences such as this $$G_{n,k} = 1 + G_{n-1,k} + G_{n-1,k-1}$$ for which I know one of the solution is $$G_{n,k}=\sum_{j=1}^k{n \choose j}$$. Now you could combine $G$ and $F$ to see if you get anywhere. I do find that many of the 2-parameter recurrences invariably has some $n \choose k$ or combination of it as one of the solution. There does seem to be multiple solutions as well. For e.g. We know that $${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$$ and from recurrence (1) $$F_{n-2,k} + F_{n-2,k-1} = F_{n-1,k}$$ we find that this is what is indicated. So you should strongly suspect that this is some $n \choose k$ or linear variations of it could be the solution... I wanted to add in your case $$=>F_{n,k}= F_{n-1,k-1} + F_{n-1,k} + F_{n-2,k-1} --> (1)$$ which seems to tell me that this is not of the linear variations $n \choose k$ form since if $$F_{n-1,k-1} + F_{n-1,k} = F_{n,k}$$, then $$=>F_{n,k}= F_{n,k} + F_{n-2,k-1}$$ $$=>F_{n-2,k-1} = 0$$ kind of unlikely...

Gopal Anantharaman
  • 447