Question

Find a big estimate for$\mathbf{\sum }_{\mathbf{j}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }\mathit{j}\mathbf{(}\mathit{j}\mathbf{+}\mathbf{1}\mathbf{)}$.

Short answer

From thedefinition of Big-O Notation $\sum _{j=1}^n j(j+1)$is $O\left(n^2\right)$with$k=1$ and$C=\frac{7}{3}$

Step-by-step solution

Definition of Big- Notation

Letfandgbe functions from the set of integers or the set of real numbers to the set of real numbers. We say that$f\left(x\right)$is$O\left(g\left(x\right)\right)$if there are constantsCandksuch that

role="math" localid="1668571597931" $\sum _{k=1}^n k=\frac{n(n+1)}{2}$

Whenever$x>k$

Formulas

The formula for sum ofnnatural number is

$\sum _{k=1}^n k=\frac{n(n+1)}{2}$

The formula for sum of square ofnnatural number is

$\sum _{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}$

Evaluating

By evaluating,$\sum _{k=1}^n k=\frac{{\displaystyle n(n+1)}}{{\displaystyle 2}}$

$$\begin{gathered} \sum _{j=1}^n j(j+1)=\sum _{j=1}^n \left(j^2+j\right) \\ =\sum _{j=1}^n j^2+\sum _{j=1}^n j \\ =\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2} \\ =\frac{n(n+1)(2n+1)+3n(n+1)}{6} \\ =\frac{n\left(2n^2+3n+1\right)+\left(3n^2+3n\right)}{6} \end{gathered}$$

$$\begin{gathered} =\frac{2n^3+3n^2+n+3n^2+3n}{6} \\ =\frac{2n^3+6n^2+4n}{6} \\ =\frac{1}{3}{n}^3+n^2+\frac{2}{3}n \end{gathered}$$

Final Solution

Let$k=1$ for,$n>1$ then,

$$\begin{gathered} \left|\sum _{j=1}^n j(j+1)\right|=\left|\frac{1}{3}{n}^3+n^2+\frac{2}{3}n\right| \\ =\frac{1}{3}{n}^3+n^2+\frac{2}{3}n \\ =\frac{1}{3}{n}^3+1\cdot n^2+\frac{2}{3}1\cdot n \\ =\frac{1}{3}{n}^3+n\cdot n^2+n\cdot n\cdot n \\ =\frac{1}{3}{n}^3+n^3+n^3 \\ =\frac{7}{3}{n}^3 \end{gathered}$$

$\left|\sum _{j=1}^n j(j+1)\right|=\frac{7}{3}\left|n^3\right|$

The constant C is$\frac{7}{3}$.

Hence by thedefinition of Big-O Notation $\sum _{j=1}^n j(j+1)$is$O\left(n^3\right)$ with $k=1$and $C=\frac{7}{3}$.