0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks, nice trick! I'm afraid I cannot extract $H$ from the resulting equation though. $\endgroup$ – omerbp Apr 7 '20 at 20:41
  • 1
    $\begingroup$ It is the one you talked about in your question that can be solved using generating functions. A lot of calculus though ! $\endgroup$ – Tuvasbien Apr 7 '20 at 20:45
  • 1
    $\begingroup$ 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! $\endgroup$ – omerbp Apr 7 '20 at 20:46

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.