An argument involving big-O notation I came across the following argument in my discrete maths textbook:
Since $n=O(n), 2n=O(n)$ etc., we have:
$$
S(n)=\sum_{k=1}^nkn=\sum_{k=1}^nO(n)=O(n^2)
$$
The accompanying question in the book is: What is wrong with the above argument?
Attempt: Performing the summation for $n=2,3$ gives:
$$
\sum_{k=1}^2k(2)\leq\sum_{k=1}^22(2)=2(2^2)=O(2^2)
$$
$$
\sum_{k=1}^3k(3)\leq\sum_{k=1}^33(3)=3(3^2)=O(3^2)
$$
Thus, it seems like the argument is correct. However, I know that I am not correct.
 A: It is a problem of quantifiers $f(n)=O(n)$ means that there exists a constant $M$ that is independant of n such that for all $n$ large enough $|f(n)| \le  Mn$. In your case, the implied constant for each term is $k$, which does depend on $n$ since it ranges between $1$ and $n$. So you cannot get this way an implied constant for the sum that does not depend on $n$.
A: $k$ is a variable that runs from $0$ to $n$, therefore in the small cases your textbook showed you, it appears to be $O(n)$, however, the ending terms of the sum are $..., (n-2)n, (n-1)n, n^2$ which are clearly not $O(n)$.  Therefore, the argument of the sum is not $O(n)$ but rather ${O(n)}^2$.  This means that the sum in question, once evaluated, is $O(n)^3$.  
A: Assuming that we have
$$
O(kn)
$$
using your logic, then we can say if $n<5$ then choosing $k = 10$ we are saying that 
$$
kn > n^2 \;\;\forall\; n 
$$
alternatively if I have $k=2$ then 
$$
kn < n^2 \;\;\forall \;n > 2
$$
so by choosing a fixed parameter we changing when $n^2$ is less than $kn$ this could be generalised to
$$
n^2 < kn \;\; \forall \;n > k
$$
this is the case when we assume that we have some notion of what $n$ is w.r.t $k$. However, the whole point of this notation is that we are saying that we have some linear relationship with the order of the iterations. If we keep letting $n$ increase regardless of $k$ (which is a constant) then we will eventually have a value of $n^2 > kn$ no matter what value of $k$ is. The big-oh notation signifies the relationship on $n$ and how the calculation scales with $n$.
To summarise if $k$ is constant then we will reach a point where
$$
O(kn) < O(n^2) 
$$
