Consider integers $m,n$ and function $f(m,n)\leq \frac{f(m-1,n-1)+f(m,n-2)}{2}$. Also, for integer $r\geq 1$ $f(m,m-r)=0$, and $f(0,n)=1$. Find a tight upper bound for $f(m,n)$.
My effort: Using the inequality and re-arranging yields: \begin{align} f(m,n)&\leq \frac{f(m-1,n-1)+f(m,n-2)}{2}\\ &\leq \frac{f(m-2,n-2)+2 f(m-1,n-3)+f(m,n-4)}{4}\\ &\leq \frac{f(m-3,n-3)+3 f(m-2,n-4)+3 f(m-1,n-5)+f(m,n-6)}{8}\\ \end{align}
I do not see a pattern that I can use. Any idea?
From the comments, using two transformations $g(m,n)=f(m,m+n)$ and$ h(m,n)=2^{m+n}g(m,2n)$, we will see $$h(m,n)=h(m−1,n)+h(m,n−1)$$
which reminds us of $h(m,n)={{m+n} \choose {n}}$. Thus, we can find something like this:
$$f(m,n)\leq {m + \lfloor{\frac{n}{2}}\rfloor \choose m} 2^{m + \lfloor{\frac{n}{2}}\rfloor}$$