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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.