* $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?




Find formula for recurrence relation with two function and two variables
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.
$$


