In some work I was doing with a colleague the following function of two natural number variables, defined by a recursion, came up and we have no clue how to solve it. Any suggestions or improvements on the upper bound given below would be appreciated. Asymptotics are also interesting.

The boundary conditions are

$$f(m,1)=2^m-1\ \text{and }\,\, f(1,n)=1.$$

The recursion for $m,n\geq 2$ is given by $$f(m,n)= f(m-1,2^{m-1}-1)+f(m,n-1)+1.$$

We can show that $f(m,n) \leq n\cdot 2^{\binom{m}{2}+1}$.

For the cases of interest to us $n\leq 2^m-1$.

  • 1
    $\begingroup$ Do I understand correctly? f(m,n) is (n-1)g(m) + 2^m - 1, where g(m) for m greater than 1 is 1+f(m-1,2^{m-1}-1)? Gerhard "Does Not Seem So Hard" Paseman, 2017.08.11. $\endgroup$ Aug 11 '17 at 15:30
  • $\begingroup$ @GerhardPaseman, I think you can separate the variables this way, but my quick napkin check doesn't get a nice recursion for $g(m)$. It seems like the coefficient of $g(m-1)$ is $2^{m-1}-2$ or something like that and then there is a non-homogeneous term but I will think about it. $\endgroup$ Aug 11 '17 at 15:50
  • $\begingroup$ I find $h(s) = (2^s-2)h(s-1) +3$ and $f(m,n)=(n-1)(h(m-1)-1) + 2^m-1$ with $h(1)=3$. This should help with asymptotics. Gerhard "Unless There Is A Mistake" Paseman, 2017.08.11. $\endgroup$ Aug 11 '17 at 17:55

First, we note that $f(m,n) - f(m,n-1)$ does not depend on $n$, so for a fixed $m$ we can write $f(m,n) = \alpha_m n + \beta_m$ for some $\alpha_m,\beta_m$ which depend only on $m$. Imposing the boundary conditions lets us write $$ f(m,n) = a_m (n-1) + (2^m-1) $$ Next, substituting that into the defining equation and simplifying gives $$ a_m = a_{m-1}(2^{m-1}-2) + 2^{m-1} $$ For example, it is easy to see that $a_2 = 2$ and $a_3 = 8$, with $$ f(2,n) = 2(n-1)+3\\ f(3,2) = 8(n-1)+7 $$

The usual trick for such recursions is to let (starting at $m=3$) $$ a_m = x_m\prod_{i=2}^{m-1}(2^i-2) $$ which gives $x_3 = a_3/(2^2-2) = 4$ and for $m>3$ $$ x_m = x_{m-1} + \frac{2^{m-1}}{\prod_{i=2}^{m-1}(2^i-2)} \\ x_m = x_3 + \sum_{k=4}^m \frac{2^{k-1}}{\prod_{i=2}^{k-1}(2^i-2)} $$ $x_m$ very rapidly approaches (from above) $\prod_{s=0}^m (1+2^{-s})$.

So $a_m$ approaches (from above) $$\frac13 \prod_{i=2}^m \frac{2^i-2}{1+2^{-i}} \rightarrow \frac13\prod_{i=2}^m (2^i-3)$$.

THis not only verifies (and slightly tightens) your relation, but also gives a handle on a lower limit, which comes from taking only one $-3$ in just one term of the product (and summing over which term uses the $-3$).

(You can actually get $x_m$ and $a_m$ in closed form, but it involves Q-Pochammer symbols and elliptic functoins so that is not at all illuminating.)

  • $\begingroup$ Thanks. I'll need a moment to think about this. Can you give me some hint where to learn about how to describe the closed form? Anyway your suggestion leads to a tighter version than what we had. $\endgroup$ Aug 11 '17 at 19:57
  • $\begingroup$ If you enter the high-$m$ value of $x_m$, which converges to 25 decimal places by the time $m=12$, as a sequence of about 20 single digits in OEIS, (the value is 4.7684620580627434829979) then the sequence is recognized as a closely related sum. One of the links in the comments is to the closed form for that number. As I hinted, that closed form is close to useless because few are familiar with the functions involved. $\endgroup$ Aug 11 '17 at 23:03

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.