# A strange two-variable recursion

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

• 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. Aug 11 '17 at 15:30
• @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. Aug 11 '17 at 15:50
• 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. 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.)
• 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. Aug 11 '17 at 23:03