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];];
  Retu开发者_如何学JAVArn[f[m, n - 1] + f[m - 1, n - 2]];]
f[3, n]

The code does not seem to work. Please help. Many thanks!

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