0

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.

BelwarDissengulp
  • 992

3 Answers3

2

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.

Sentient
  • 675
1

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

DanielWainfleet
  • 57,985
0

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.

Penguino
  • 1,169
  • 6
  • 10