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



A strange two-variable recursion
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.)


