0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.$

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

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.

$\endgroup$
  • $\begingroup$ In the last equation, the denominator should read $\mathcal{O}(k^3)^2$, no? $\endgroup$ – Sentient Aug 2 '18 at 0:57
  • $\begingroup$ @Sentient. Agreed............ $\endgroup$ – DanielWainfleet Aug 2 '18 at 0:59
  • $\begingroup$ @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. $\endgroup$ – Penguino Aug 2 '18 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.