HackerRank: Summing the N series

Finally a problem where we need a little bit of math to solve it. It is called Summing the N series, and when I say a little bit, I mean only a little bit. The problem reads

You are given a sequence whose  term is

 

You have to evaluate the series

 

Find .

Bruteforce solution to Summing the N series

We could try to just bruteforce a solution like this

sum = 0
for i in range(1, n+1):
    sum += i*i - (i-1)*(i-1)

return sum % 1000000007    

However, as n can go up to 10^16, that is not really a viable solution and when I tried I got a timeout on most of the problems evaluated. So lets look at the series.

Expanding the series

If we write out the last few terms of we get

As we can see the terms cancel out so we only have the first term of minus the last term of when summing the whole series. However the last term of . Therefore we end up with

and thus we can write the code as

return n*n % 1000000007