# Find a recursive function

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?

• Define $g(m,n) = f(m, m+n)$, rewrite the inequality in terms of $g$, and change it into an equality. The resulting equation will look similar (but not identical) to the recursion for $m\choose n$. Try to figure out how you can express $g(m,n)$ using the choice function. – Paul Sinclair Oct 19 '17 at 23:18
• @paulsinclair thanks. i did it, but was not able to relate it to the choose function. can you help more? – Susan_Math123 Oct 19 '17 at 23:49
• Try another transformation: $h(m,n) = 2^{m+n}g(m, 2n)$ – Paul Sinclair Oct 20 '17 at 3:04
• @kobe Hi Kobe, any idea how to solve this? – Susan_Math123 Oct 20 '17 at 4:25
• The first was just an obvious simplification of your original problem. The 2nd was designed to remove the division by $2$ and the double-drop in the index $n$. But by my calculations (which I didn't double-check), it leads to $h(m,n) = h(m-1,n) + h(m, n-1)$, which should be $m+n\choose n$. Note, though, that it only gives you the upper bound for $f(m,n)$ for even $n$. You will have to modify it to handle odd $n$. – Paul Sinclair Oct 20 '17 at 16:18

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}$$