# Big-O notation and growth of a squared sum

While solving a problem I got the following expression:

$$\frac{\sum_{k=1}^{n}k^{4}}{\left(\sum_{k=1}^{n}k^{2}\right)^{2}}$$

My goal is to find out if this expression goes to $0$ when $n \to \infty$.

Using Faulhaulber's formula, we get

$$\sum_{k=1}^n k^{p} = \frac{n^{p+1}}{p+1}+\frac{1}{2}n^p+\sum_{k=2}^p \frac{B_{k}}{k!}p^\underline{k-1}n^{p-k+1}$$ Thus using Big-O notation, this is $\mathcal{O}(n^{p+1})$. Is $(\sum_{k=1}^n k^{p})^{2}$ $\mathcal{O}(n^{2(p+1)})$? I squared Faulhaulber's formula and it seems right, however I'd like a confirmation, thank you very much.

## 3 Answers

Not necessarily a valid proof for demonstrating the sum of powers of degree $k$ is in $\Theta(n^{k+1})$, but hopefully this provides intuition to @Penguino's answer. We start off by assuming $j \geq k$, taking the last term of the sum as our lower bound.

\begin{aligned} \sum_{i=1}^{n} i^k = \Theta(n^{j}) &\implies \frac{d^{k+1}}{dn^{k+1}}(\sum_{i=1}^{n} i^k = \Theta(n^{j})) \\ &\implies 0 = \Theta(n^{j-k-1})) \\ \end{aligned}

As $0 \in \Theta(1)$ and $1 = n^0 = n^{(k + 1) - k - 1}$, the last statement implies $j = k + 1$. And thus, $$\sum_{i=1}^{n} i^k = \Theta(n^{k + 1})$$

You can combine this, with the product property of Big-$\mathcal{O}$ notation,

$$\text{If }\ f_1 = \mathcal{O}(g_1) \text{ and }\ f_2 = \mathcal{O}(g_2), \text{ then }\ f_1f_2 = O(g_1g_2).$$

to find your answer.

• Really didactic, thank you very much! – Sergio Andrade Aug 2 '18 at 1:19

There are many ways to show that $\sum_{k=1}^n k^r=O(n^{r+1})$ as $n\to \infty,$ when $r>0.$

For example $\sum_{k=1}k^r$ is bounded above by $\int_1^{n+1}x^rdx= ((n+1)^{r+1}-1)/(r+1)$ and is bounded below by $\int_0^n x^rdx=n^{r+1}/(r+1).$

Because $\int_{k-1}^kx^rdx < k^r<\int_k^{k+1}x^rdx.$

• One peculiarity is that $\sum_{k=1}^nk^3= (\sum_{k=1}^nk)^2$ which at first glance looks like a mistake. – DanielWainfleet Aug 2 '18 at 1:14

Generally

$$\sum_{k=1}^{n}k^{m}$$

approximates to

$$O(k^{m+1})$$

so your problem should look like

$$O(k^{4+1})/O(k^{3})^{2}=O(k^{5})/O(k^{6})$$

I would expect it to tend to zero.

• In the last equation, the denominator should read $\mathcal{O}(k^3)^2$, no? – Sentient Aug 2 '18 at 0:57
• @Sentient. Agreed............ – DanielWainfleet Aug 2 '18 at 0:59
• @Sentient you are correct. That is what I began to say but miss-typed, then read my miss-typing and came to the exactly wrong solution. Corrected now. – Penguino Aug 2 '18 at 2:36