# Upper bound for reccurence relation with two variables, with linear dependency between them

Given the following reccurence relation:

$$T(M,k) = T(M-1,k)+T(M-2,k-1)$$

where $$T(0,k)=0, T(1,k)=1, T(M,1)=1$$

I have $$M^k$$ as a general upper bound for $$T(M,k)$$.

Now, suppose I want to give an upper bound only for cases where $$M=n \cdot k$$, i.e. I have the following new definition: $$R(n,k) = T(nk,k)$$ and $$R(n,1) = n-1$$, $$R(2,k)=f(k)$$ (where $$f(k)$$ is some function of $$k$$ I know how to bound for any $$k$$).

is there a way to give an upper bound for $$R(n,k)$$, expressed with $$n$$ and $$k$$, which will by tighter than just placing it in $$M^k$$? I suspect that for those cases where $$M=nk$$ the value of $$T$$ is much lower than $$M^k$$, so a tighter bound should exists.

Is there a way to do such thing? I tried to unfold $$R(n,k)$$ to get an explicit definition but I get stucked when I need to express $$T(nk-1,k)$$ and $$T(nk-2,k-1)$$, since they do not "fit" to the defenition of $$R(n,k)$$.