# Big-O notation and polynomials

In my text, I am given that the sum of the first n positive integers can be understood in terms of big-O notation.

''Since each of the integers in the sum of the first $n$ positive integers does not exceed $n$'', we can write:

$$1 + 2 + \cdots + n \leq n + n \cdots + n= n^2$$

Why does $n + n +\cdots + n = n^2$ ?

• Try it with some small numbers first: $$1 + 2 + 3 < 3 + 3 + 3 = 3 (1 + 1 + 1) = 3^2.$$ – Antonio Vargas Apr 9 '14 at 17:59
• How many $n$'s are there? – Hurkyl Apr 9 '14 at 17:59
• @AntonioVargas hmm, so because there are three terms on the left side of the inequality, and three terms on the right, we can say that the "..." represents the same amount, so it's just 3(1 + 1 + 1)? what if there were another 1? – compguy24 Apr 9 '14 at 18:06
• Yes, it's implied that the number of terms on both sides of the $<$ sign is the same. – Antonio Vargas Apr 9 '14 at 18:07

## 2 Answers

We have that:

$$n+\underbrace{\cdots}_{n-2}+n=n^2=n\times n$$

from simple arithmetic (multiplying $n$ by $m$ can be viewed as adding $m$ lots of $n$). With regards to the validity of the statement $\sum_{i=1}^{n}i<n^{2}$ we can examine the closed form for the summation:

$$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\frac{1}{2}(n^{2}+n)$$

We can see that this is strictly less than $n^2$ for $n> 1$ by observing that $n<n^{2}$ for $n>1$ and that $\frac{1}{2}(1^{2}+1)=1$ so the inequality does not hold for $n=1$.

To see why $n+n+...+n=n^2$, consider this:

The multiplication of two whole numbers is equivalent to the addition of one of them with itself as many times as the value of the other one; for example, 3 multiplied by 4 (often said as "3 times 4") can be calculated by adding 4 copies of 3 together:

$3 \times 4 = 3 + 3 + 3 + 3 = 12$

Remember the explanation of multiplication you learned back in grade school! Ask yourself why we say 3 times 4... the wording is not arbitrary - we are literally adding 3, 4 times. Equivalently adding $n$ copies of $n$ is equivalent to saying $n$ times $n$, or $n^2$.