Given a recurrence relation $f(x, y) = 2 \times f(x-1, y) + 4\times f(x - 1, y - 1)$ for $x, y \geq 1$, otherwise $f(x,y) = 1$. Find the closed-form solution of $f(x,y)$ for all $x$ and $y$.

I tried to calculate a few values, but I can't recognize a pattern from these values, apart from $f(x,y) = 6^x$ for $1 \leq x \leq y$ $$\begin{array}{c|cc} x\backslash y&0&1&2&3\\ \hline 0&1&1&1&1\\ 1&1&6&6&6\\\ 2&1&16&36&36\\ 3&1&36&136&216\\ \end{array}$$

I read several questions similar from this but it didn't fit my question well. Can someone lend me a help on this?

  • 2
    $\begingroup$ If that may help: setting $f(x,y)=2^{x+y}g(x,y)$ turns your recurrence into Pascal's identity $g(x,y)=g(x-1,y)+g(x-1,y-1)$ with modified boundary conditions $f(x,0)=2^{-x},f(0,y)=2^{-y}$. $\endgroup$ – Yves Daoust Nov 26 '16 at 10:03
  • 1
    $\begingroup$ If you define $h(x,y)=f(x+y,y)$ (which for $x,y\geq 0$ generates the lower-triangular part of your table) then the recurrence relation modifies to $h(x,y)=2h(x-1,y)+4h(x,y-1)$. This has the advantage that $x,y$ are decremented seperately. (Not sure that's enough to make this easily solvable, though...) $\endgroup$ – Semiclassical Nov 26 '16 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.