# Solving recurrence relation in 2 variables plus constant

I've encountered this question, asking to solve the recurrence $$F(n,m) = F(n-1,m) + F(n,m-1)$$ for some initial conditions. I wonder how the solution would change if we add a constant, say

$$G(n,m) = G(n-1,m) + G(n,m-1)+2$$.

One answer for the mentioned post suggested generating functions. What would change here? For simplicity, let's assume $$G(1,m) = m − 1$$ and $$G(n, 1) = 0$$.

## 1 Answer

Let $$H(n,m)=G(n,m)+2$$, then \begin{aligned} H(n,m)&=G(n,m)+2 \\ &=G(n-1,m)+G(n,m-1)+4 \\&=(G(n-1,m)+2)+(G(n,m-1)+2) \\&=H(n-1,m)+H(n,m-1) \end{aligned} You can now solve the recurrence for $$H$$ and deduce the recurrence for $$G$$ by writing $$G(n,m)=H(n,m)-2$$.

• Thanks, nice trick! I'm afraid I cannot extract $H$ from the resulting equation though. – omerbp Apr 7 '20 at 20:41
• It is the one you talked about in your question that can be solved using generating functions. A lot of calculus though ! – Tuvasbien Apr 7 '20 at 20:45
• Yeah, tried to use the method vonbrand gave in that post, but it's non-trivial to find an analytic solution. Will spend some time on it... Thanks again! – omerbp Apr 7 '20 at 20:46