Явную формулу надо искать в виде
где

- целые числа (обычно это произведение каких-нибудь биномиальных коэффициентов).

надо подбирать с таким расчётом, чтобы можно было написать
т.е. по

можно явно просуммировать.
Если явная формула найдена, то существует алгоритм, позволяющий находить

(Gosper summation algorithm). Вся проблема в том, чтобы найти эту формулу (возможно, существует алгоритм, позволяющий находить её, но мне он неизвестен).
Добавлено спустя 17 минут 48 секунд:
Возможно как-то поможет диффур для производящей функции
