1

$\sum\limits_{i=1}^n(3i+2n)$ is $O(n^2)$

How do I solve this? I know that the answer for $\sum\limits_{i=1}^n(3i+2n)$ would be $$\sum\limits_{i=1}^n(3i+2n)=\sum\limits_{i=1}^n3i+\sum\limits_{i=1}^n2n=3\sum\limits_{i=1}^ni+2n\sum\limits_{i=1}^n1=3\frac{n(n+1)}{2}+2n\cdot n=3\frac{n(n+1)}{2},$$ but how do I solve $\sum\limits_{i=1}^n(3i+2n)$ is $O(n^2)$ ?

user1688953
  • 13
  • 1
    I've formatted your question so that it is actually readable. I tried not to make any changes to the content of your post, but much of what you wrote was very difficult to interpret. Please make sure that my edits were correct and if not tell me where I have misinterpreted you so I can remedy the problem. I'm particularly concerned about the last equality (which is clearly false, but is the best guess I could make as to what you meant). – Alex Becker Mar 25 '13 at 19:54
  • 1
    Related. – Cameron Buie Mar 25 '13 at 19:55

3 Answers3

1

You want to show that there exists some real number $C$ such that $\sum\limits_{i=1}^n(3i+2n)\leq Cn^2$ for sufficiently large $n$. Try splitting this up as $$\sum\limits_{i=1}^n(3i+2n)=\sum\limits_{i=1}^n3i+\sum\limits_{i=1}^n2n=3\frac{n(n+1)}{2}+2n^2$$ and observe that $\frac{n(n+1)}{2}=\frac{n^2+n}{2}\leq \frac{2n^2}{2}=n^2$, so using $C=5$ works.

Alex Becker
  • 60,569
  • thank you so much for the explanation, so it basically prove by induction? – user1688953 Mar 25 '13 at 20:01
  • @user1688953 There's no need to resort to induction. Where were you thinking induction is needed? – Alex Becker Mar 25 '13 at 20:07
  • Sorry I am just very confused in this unit,I was thinking to establish that a given statement is true for all natural numbers, but I can see that I was looking at the question the wrong way. – user1688953 Mar 25 '13 at 20:12
  • @user1688953 You are establishing that a given statement is true for all natural numbers - but induction is just one of many means to do that; this is simply using direct calculation to the same end. – Steven Stadnicki Mar 25 '13 at 21:26
1

A very fast way to show the result is: $$\sum\limits_{i=1}^n(3i+2n)\leq \sum\limits_{i=1}^n 5n=5n^2 =O(n^2)$$

0

We are interested in estimating $\sum_{i=1}^n (3i+2n)$. This is equal to $$\sum_{i=1}^n 3i+\sum_{i=1}^n 2n.$$

The second sum is the sum of $n$ terms, each of which is $2n$. So the second sum is $2n^2$.

For the first sum, we can get an exact expression, as in your work. But let's not work so hard. We have a sum of $n$ terms, each of which is $\le 3n$. So $\sum_{i=1}^n 3i\le 3n^2$.

Thus our original sum is $\le 5n^2$. We could have done this in one step by noting that $3i+2n\le 5n$ for all $i\le n$.

So there is a constant $C$, namely $5$, such that our sum is $\le Cn^2$ for all $n$. That ends the proof.

Remark: In this case, by using the standard formula for $\sum_{i=1}^n i$, we can get a "better" constant than $5$. But it can save a lot of work if one notices when a crude estimate is good enough.

André Nicolas
  • 507,029