Как решить рекурсивные отношения аналитически в Mathematica?

Question

Например, у меня есть следующая рекурсия, и я хочу получить 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]

Код, похоже, не работает. Пожалуйста помоги. Большое спасибо!

Answer 1

У вас есть бесконечная рекурсия, потому что когда m не инициализирован, ни один из граничных случаев не совпадает.

Вместо использования Return вы получите более предсказуемое поведение, если будете использовать функциональное программирование, т.е.

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]
  ]

В этом случае Which не может решить, какой вариант использовать с n не инициализирован, поэтому f[3, n] вернет выражение.

Один из способов получить формулу - с помощью RSolve.Не похоже, что это может решить это уравнение в полной общности, но вы можете попробовать его с одной фиксированной переменной, используя что-то вроде этого

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

В результате вы увидите K[1], что является произвольной итерациейпеременная и C[1], которая является свободной константой.Это потому, что не указан граничный случай