Find formula for recurrence relation with two function and two variables 
*

*$f(n,k) = 2g(n-2,k-1)+f(n-1,k)$

*$g(n,k) = g(n-1,k-1)+f(n,k)$

*when $n\le0$ or $k\le0: \quad f(n,k) = 0$

*when $n < k:\quad f(n,k) = 0$

*when $n-k<-1:\quad  g(n,k) = 0$

*when $k=0:\quad  g(n,k) = 1$

*$g(1,1) = 3$


Solve the above recurrence relation for two variable and two equations.  More formally, How can we solve a homogeneous recurrence relation in 2 variables?

 A: A quick way is to generate the first few values and guess the solution, then check that it's correct.  Using FriCAS, for example:
(1) -> )se fu ca all
   In general, interpreter functions will cache all values.
(1) -> f(n,k) == (if n < k or n <= 0 or k <= 0 then 0 else 2*g(n-2,k-1)+f(n-1,k))
                                                                   Type: Void
(2) -> g(n,k) == (if n+1 < k then 0 else (if k = 0 then 1 else g(n-1,k-1)+f(n,k)))
                                                                   Type: Void
(3) -> l := [guessRat([(f(n,k)) for n in k..2*k+1], indexName=="m").1 for k in 1..];
   Compiling function g with type (Integer, Integer) -> 
      NonNegativeInteger 
   g will cache all previously computed values.
   Compiling function f with type (Integer, Integer) -> 
      NonNegativeInteger 
   f will cache all previously computed values.

                                            Type: Stream(Expression(Integer))
(4) -> guessPRec([(l.i)::FRAC POLY INT for i in 1..20])

   (4)
   [
     [f(n): (n + 3)f(n + 2) + (- 2 m - 2)f(n + 1) + (- n - 1)f(n) = 0,
                                2
      f(0) = 2 m + 2, f(1) = 2 m  + 4 m + 2]
     ]
                                              Type: List(Expression(Integer))
(5) -> Feq := guessHolo(cons(0, [(l.i)::FRAC POLY INT for i in 1..20]), functionName=="F").1

   (5)
      n         2      ,
   [[x ]F(x): (x  - 1)F (x) + (2 m + 2)F(x) + 2 m + 2 = 0,

                                                 3       2             3
                            2            2   (4 m  + 12 m  + 14 m + 6)x       4
    F(x) = (2 m + 2)x + (2 m  + 4 m + 2)x  + --------------------------- + O(x )
                                                          3
     ]
                                                    Type: Expression(Integer)
(6) -> )expose RECOP
   RecurrenceOperator is now explicitly exposed in frame frame1 
(6) -> eq := getEq Feq

          2      ,
   (6)  (x  - 1)F (x) + (2 m + 2)F(x) + 2 m + 2

                                                    Type: Expression(Integer)
(7) -> F := operator 'F;

                                                          Type: BasicOperator
(8) -> solve(eq, F, x=0, [0])

                   m log(x + 1) - m log(x - 1)              - m log(- 1)
        (- x - 1)%e                            + (- x + 1)%e
   (8)  ----------------------------------------------------------------
                                       - m log(- 1)
                              (x - 1)%e
                                         Type: Union(Expression(Integer),...)

Rewriting the above in human readable form, we obtain
$$
F_n(x) := \sum_k f(n+k, k) x^k = \left(\frac{1+x}{1-x}\right)^{n+1} - 1.
$$
A: Consider the generating functions  $F_n:=\sum_{k\in\mathbb{Z}} f(n,k)x^k$ and $G_n:=\sum_{k\in\mathbb{Z}} g(n,k)x^k$. The given equations then read:


*

*$F_n=2xG_{n-2}+F_{n-1}$

*$G_n=xG_{n-1}+F_{n}$

*$F_n = 0$ for all $n\le0$

*$F_n\in\mathbb{R}[x]$ and $\operatorname{deg}F_n\le n$

*$G_n\in\mathbb{R}((1/x))$ and $\operatorname{deg}G_n\le n+1$

*$[x^0]G_n  = 1$

*$[x^1]G_1 = 3$
The first two of these imply that both $F_n$ and $G_n$ satisfy the same three-terms linear recurrence:
$$F_n-(x+1)F_{n-1}-xF_{n-2}=0$$
$$G_n-(x+1)G_{n-1}-xG_{n-2}=0$$
which would imply for both a general form $$\alpha\Big({x+1+\sqrt{x^2+6x+1}\over2}\Big)^n+\beta\Big({x+1-\sqrt{x^2+6x+1}\over2}\big)^n.$$
However, if you want condition (3), that is $F_n=0$ for all $n<0$, then $F_n=0$ for all $n\in\mathbb{Z}$ too, but then all $G_n$ must vanish too, what is incompatible with the last requirements. 
