Recurrence $f(a,b)=f(a,b-1)+2f(a-1,b-1)$

Question

Consider the recurrence relation $$f(a,b)=f(a,b-1)+2f(a-1,b-1)$$ for integers $a,b\geq 2$, where $f(a,b)=1$ if $a=1$ or $b=1$.

Is it possible to find a closed form for $f(a,b)$?

Answer 1

For ease, define $k=a-1, n=b-1$. Then we can write the recurrence in terms of these indices and $g(k, n) = f(a, b)$ as $$g(k, n) = g(k, n-1)+2g(k-1, n-1) \quad \forall k, n >0, \qquad g(0, n) = g(k, 0) = 1$$

For each $n=1, 2, 3, ...$, let $\displaystyle G_n(x) = \sum_{k \ge 0} g(k, n)x^k$. We have $G_0(x) = \dfrac1{1-x}.$

Multiplying the recurrence relation with $x^k$ and summing over $k \ge 1$, we get $$G_n(x)-1 = \left( G_{n-1}(x)-1 \right)+ 2x G_{n-1}(x) $$

$$\implies G_n(x) = (1+2x)G_{n-1}(x) = \frac{(1+2x)^n}{1-x} = \left(\sum_i \binom{n}{i} 2^i \cdot x^i\right)\left(\sum_{j\ge 0}x^j\right)$$

$$\implies g(k, n) = \sum_{i=0}^k\binom{n}{i}2^i $$

In terms of our original indices this $\displaystyle \implies f(a, b) = \sum_{i=0}^{a-1}\binom{b-1}{i}2^i \tag{1}$

This expression holds for all values of $a, b$. As a partial sum of the binomial series, I am not sure if you will find a closed expression for this sum over the entire domain (at least unless you use the hypergeometric function as Mathematica suggests $3^{b-1}-2^a \binom{b-1}{a}\cdot {}_2F_1(1,1+a-b,1+a,-2)$)

Note for $a\ge b$, the last expression (or the sum in $(1)$) reduces to $3^{b-1}$.

Answer 2

If $a>b$, you can put $f(a,b)=3^{b-1}$.

I came up with this solution by copying an approach I use in the "one-variable" case. You can replace $f(a,b)$ with $x^ay^b$ and you work out the algebra, the expression $x^ay^b=x^ay^{b-1}+2x^{a-1}y^{b-1}$ gives you that $xy=x+2$ and the edge conditions are $x^a y=1$, $x y^b=1$ so that, when $a>b$ you have $x^ay^b= (xy)^{b-1}x^{a-b+1}y=(x+2)^{b-1}$. Since $xy=1$, you get $x=x (xy) = x^2 y = 1$. Putting that in the previous expression you get $f(a,b)=3^{b-1}$.

Of course this is not a rigorous approach, but you can try if the solution you get satisfies the recurrence and this is the case in this example.

Answer 3

This is really just a long comment, but it might help. Quimey is quite right that $f(a,b)=3^{b-1}$ if $a\gt b$ (actually if $a\ge b$). For fixed $a$, the sequences are

$$\begin{align} &1,1,1,1,1,1,\ldots\\ &1,3,5,7,9,11,\ldots\\ &1,3,9,19,33,51,73,\ldots\\ &1,3,9,27,65,131,\ldots\\ &1,3,9,27,81,211,\ldots\\ \end{align}$$

The first two non-obvious of these are A058331 and A161712 in the OEIS. The final one does not appear there (yet).