0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Paul Sinclair Oct 19 '17 at 23:18
  • $\begingroup$ @paulsinclair thanks. i did it, but was not able to relate it to the choose function. can you help more? $\endgroup$ – Susan_Math123 Oct 19 '17 at 23:49
  • 1
    $\begingroup$ Try another transformation: $h(m,n) = 2^{m+n}g(m, 2n)$ $\endgroup$ – Paul Sinclair Oct 20 '17 at 3:04
  • $\begingroup$ @kobe Hi Kobe, any idea how to solve this? $\endgroup$ – Susan_Math123 Oct 20 '17 at 4:25
  • 1
    $\begingroup$ 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$. $\endgroup$ – Paul Sinclair Oct 20 '17 at 16:18
0
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.