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)$.