Proving an equivalent to a summation formula

Question

Let us recall the summation formula

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

How do we show that

$$\sum_{k=1}^nk=\frac{1}{2}n^2+\mathcal{O}(n) ?$$

I started by stating the definition of "big-o" notation where we let $f$ and $g$ be two functions defined on a domain $D\subseteq\mathbb{R}$ that is not bounded above. We write that $f(n)=\mathcal{O}(g(n))$ if there exists a positive constant $c$ such that $$\forall n\geq n_0, \ |f(n)|\leq c|g(n)|, $$ for some $n_0\in \mathbb{N}.$

I think that the positive constant is this $c=\frac{1}{2}n^2$.

So, the sequence would therefore me the summation formula? I do not know how to adequately approach this problem.

$$\frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$$So you can take $c = 1/2$ and $n_0 = 1$. — , Apr 16 '16 at 05:59
Surely you can see that $c = \frac{1}{2}n^2$ won't work, because that isn't a constant. — , Apr 16 '16 at 06:00

score 1 · Accepted Answer · answered Apr 16 '16 at 07:03

Showing that $$\sum_{k=1}^nk=\frac{1}{2}n^2+\mathcal{O}(n)$$ is the same as showing that $$\left(\sum_{k=1}^nk\right)-\frac{1}{2}n^2=\mathcal{O}(n).\tag1$$ The LHS of (1) equals $\frac n2$, by the summation formula, so now you have to show that $$ \frac n2 = {\mathcal O}(n). $$ Using the $f$, $g$ notation, we have $f(n):=\frac n2$, and $g(n):=n$. For what value of $c>0$ do we have $|f(n)|\le c|g(n)|$ for all large $n$?

Proving an equivalent to a summation formula

1 Answers1