# How to solve recursion relations analytically in mathematica?

For example, I have the following recursion and I want to get f[3,n]:

``f[m_, n_] := Module[{}, If[m < 0, Return[0];];If[m == 0, Return[1];];If[2*m - 1 >= n, Return[0];];If[2*m == n, Return[2];];If[m == 1, Return[n];];Return[f[m, n - 1] + f[m - 1, n - 2]];]f[3, n]``

You have an infinite recursion because when `m` is not initialized, none of the boundary cases match.

Instead of using `Return` you'll get more predictable behavior if you use functional programming, ie

``````f[m_, n_] := Which[
m < 0, 0,
2 m - 1 >= n, 0,
2 m == n, 2,
m == 1, n,
True, f[m, n - 1] + f[m - 1, n - 2]
]
``````

In this case `Which` can not decide which option to take with `n` not initialized, so `f[3, n]` will return an expression.

One way to get a formula is with `RSolve`. Doesn't look like it can solve this equation in full generality, but you can try it with one variable fixed using something like this

``````Block[{m = 3},
RSolve[f[m, n] == f[m, n - 1] + f[m - 1, n - 2], f[m, n], {n}]
]
``````

In the result you will see `K[1]` which is an arbitrary iteration variable and `C[1]` which is a free constant. It's there because boundary case is not specified