[Algorytmy][Rekurencja] Wzór rekurencyjny i jawny

[Sourcerer]

Witam potrzebuję pomocy w rozwiązaniu zadania:

Napisac wzór rekurencyjny liczby kroków działania nastepującego algorytmu, gdzie zakładamy, że
operacją dominujacą jest operacja print. Metodą funkcji tworzących znaleźć wzór jawny.

Kod: Zaznacz cały

def b(n):
   if (n!=0):
      for i in [1,2,...,n]:
          for j in [1,2,...,i]:
             print (i,j)
      b(n-1)

Do tego podana jest podpowiedź: \(\displaystyle{ 1 ^{2} + 2 ^{2} + . . . + n ^{2} = \frac{n(n+1)(2n+1)}{6}}\)

Dziękuję za pomoc.

[bartek118]

\(\displaystyle{ b(0) = 0 \\
b(n) = \sum_{i = 1}^{n} \sum_{j = 1}^{i} 1 + b(n-1)}\)

Czyli \(\displaystyle{ b(n) = \sum_{i = 1}^{n} \sum_{j = 1}^{i} 1 + b(n-1) = \sum_{i = 1}^{n} i + b(n-1)}\)