Okay so I understand how to find the upperbound and lowerbound and hence theta for some simple functions like 4n + 5nlgn + 6 but what I don't understand is how to do it for the following function

1 + 2 + ... + n

I understand to find the upperbound you do the following steps

1 + 2 + ... + n ≤ n + n + ... + n x n = n^2 for all n ≥ 1

I understand why we substitute n but where does the n x n come from? (I got this example out of my text book)

I want to know this so I can solve

n + 2n + 3n + ... + n^2

I believe I would do something like this

n + 2n + 3n + ... + n^2 ≤ n^2 + n^2 + n^2 + ... + n^2 x n^2 = n^4 for all n ≥ 1?

Or is it

n + 2n + 3n + ... + n^2 ≤ n^2 + 2n^2 + 3n^2 + ... + n^2 x n^2 = ??? for all n ≥ 1?

Also, is the upperbound n^4 or am I not on the right track at all?

Basically I'm just trying to figure out how to find the upperbound at the moment and then I will attempt to find the lowerbound. I've been puzzling over this for a while and would really appreciate it anyone could help.

Thanks.