Suma elementów trójkąta, suma szeregu

Witam zadanie z codewars.
link

Po wszystkim dochodzę do wniosku że rozwiązaniem jest suma od 0 do n gdzie n<=1 000 000 liczona według wzoru
(n+1)*(2n+1)
Jak oszacować wartość takiej sumy tzn jaki jest jej wzór ogólny. Mogę prosić o pmoc.
Sumowanie w pętli odpada. Dla dużych n program przekracza czas wykonania na serwerze.

https://www.wolframalpha.com/input?i=sum+%28sum+2*j%2Bi%2B1+from+i%3Dj+to+n%29+from+j%3D0+to+n

https://www.wolframalpha.com/input?i=1%2F6+%281+%2B+n%29+%286+%2B+11+n+%2B+4+n%5E2%29+for+n+%3D+3

Dziekuję rozwiązanie jest OK. Program przeszedł testy.

Sympy jest też dobrym narzędziem do obliczeń symbolicznych: python -c "from sympy import *; i,j,n=symbols('i,j,n'); print(Sum(Sum(2*j+i+1, (i, j, n)), (j, 0, n)).doit().simplify())"

Suma od 0 do n to upraszając wzór na sumę ciągu arytmetycznego to (n+1)*n/2.