Big theta of summation
Solution 1
First note that it is sufficient to prove that $f(n) \in \mathcal{O}(1)$, since $f(n)$ is trivially in $\mathcal{\Omega}(n)$. Next note that $$\sum_{k=1}^n k^3 x^k < \sum_{k=1}^{\infty} k^3x^k = S(x) \,\,\,\,\,\,\,\,\, \forall x \in (0,1)$$ Hence, if we prove that $S(x) \in \mathcal{O}_x(1)$, we are done, where $\mathcal{O}_x(1)$ indicates that the constant depends on $x$.
Recall that $$\sum_{k=1}^{\infty} x^k = \dfrac{x}{1x} = \dfrac1{1x}  1$$ Differentiating term by term, with $x \in (0,1)$, we get that $$\sum_{k=1}^{\infty} kx^{k1} = \dfrac1{(x1)^2} \implies \sum_{k=1}^{\infty} kx^{k} = \dfrac{x}{(x1)^2} = \dfrac1{x1} + \dfrac1{(x1)^2}$$ Again differentiating term by term we get that $$\sum_{k=1}^{\infty} k^2x^{k1} = \dfrac1{(x1)^2}  \dfrac2{(x1)^3}$$ Hence, $$\sum_{k=1}^{\infty} k^2x^{k} = \dfrac{x}{(x1)^2}  \dfrac{2x}{(x1)^3} = \dfrac1{x1}  \dfrac3{(x1)^2}  \dfrac2{(x1)^3}$$ Differentiate this again to get that $$\sum_{k=1}^{\infty}k^3 x^{k1} = \dfrac1{(x1)^2} + \dfrac6{(x1)^3} + \dfrac6{(x1)^4}$$ Hence, $$\sum_{k=1}^{\infty}k^3 x^{k} = \dfrac{x}{(x1)^2} + \dfrac{6x}{(x1)^3} + \dfrac{6x}{(x1)^4} \in \mathcal{O}_x(1) \,\,\,\,\,\, \forall x \in (0,1)$$ Take $x= \dfrac12$ to get what you want.
Solution 2
Here is a handson approach: for every positive $x$, $x\lt2^x$ hence $x\lt4\cdot2^{x/4}$, which implies that $x^3\lt64\cdot2^{3x/4}$. Thus, $f(n)\leqslant64\sum\limits_{k\geqslant1}2^{k/4}\lt64/(12^{1/4})$, which is finite. Now, the assertion $f(n)=\Theta(1)$ simply means that the sequence $(f(n))_n$ is bounded, hence we are done.
More generally, for every $r\lt1$ and every $a$, $\sum\limits_{k\geqslant1}k^ar^k$ converges.
Related videos on Youtube
Jo Dane
Updated on January 30, 2020Comments

Jo Dane about 3 years
I had a quick question with which I am not sure how to get started. I've done some time complexity stuff that involves bigoh, omega and theta notation but nothing with sums.
Here is the question: $$ f(n) = \sum_{k=1}^n {k^{3}\over2^{k}} $$
Prove that $$ f(n) = \Theta(1) $$
Any tips, advice or answers to similar questions would be appreciated. Thanks.