Я давно, так сказать, придумал такой способ решения подобной задачи. Поясню на примере. Допустим, нам нужно вычислить сумму

. Допустим, она равна многочлену 2+1 -ой степени от

:

. Тогда, если в этой формуле заменить

на

, мы снова получим верную формулу. Затем вычитаем почленно из второго равенства первое, дальше метод неопределенных коэффициентов + значение при

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