6.2.3 Кратные суммы

Задача. Для заданных $n > 0$ и $m > 0$ вычислить сумму $$S(n,m) = \sum_{i_1=1}^m \sum_{i_2=1}^m \ldots \sum_{i_n=1}^m1/(\sum_{j=1}^n i_j).$$

Решение. Введем в рассмотрение функцию

$$T(n,m,c) = \sum_{i_1=1}^m \sum_{i_2=1}^m \ldots \sum_{i_n=1}^m1/(c + \sum_{j=1}^n i_j).$$

Тогда $S(n,m) = T(n,m,0)$ и

$$T(n,m,c) = \sum_{k=1}^m (\sum_{i_1=1}^m \sum_{i_2=1}^m \ldots\sum_{i_{n-1}=1}^m 1/((c+k) + \sum_{j=1}^{n-1} i_j))=$$

$$=\sum_{k=1}^m T(n-1,m,c+k)$$

при $n > 0$. При $n=0$ имеем $T(0,m,c) = 1/c$.

Рекурсивное определение функции T можно записать на языке Zonnon.

module КратныеСуммы;
    var M,N : integer;
    procedure T (N,M,C : integer): real;
          var I : integer; Сумма : real;
    begin Сумма := $\emptyset$;
          if N > 0 then
              for I := 1 to M do Сумма := Сумма + T(N-1,M,C+I) end;
              T := Сумма  (* {Сумма = Т(N,M,C)} *)
          else T := 1/C  (* {= T(0,M,C)} *)
    end T;
begin
    read(N,M); writeln('S(',N,',',M,')=',T(N,M,0))
end КратныеСуммы.

Для доказательства окончания этой программы заметим, что всякий вызов функции Т с положительным первым параметром приводит к M вызовам с меньшим на 1 значением первого параметра. Это значит, что в конце концов мы придем к вызовам функции Т с нулевым значением первого параметра, которые уже не порождают никаких вызовов.