Big theta of summation

summation

4,626

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}{1-x} = \dfrac1{1-x} - 1$$ Differentiating term by term, with $x \in (0,1)$, we get that $$\sum_{k=1}^{\infty} kx^{k-1} = \dfrac1{(x-1)^2} \implies \sum_{k=1}^{\infty} kx^{k} = \dfrac{x}{(x-1)^2} = \dfrac1{x-1} + \dfrac1{(x-1)^2}$$ Again differentiating term by term we get that $$\sum_{k=1}^{\infty} k^2x^{k-1} = -\dfrac1{(x-1)^2} - \dfrac2{(x-1)^3}$$ Hence, $$\sum_{k=1}^{\infty} k^2x^{k} = -\dfrac{x}{(x-1)^2} - \dfrac{2x}{(x-1)^3} = -\dfrac1{x-1} - \dfrac3{(x-1)^2} - \dfrac2{(x-1)^3}$$ Differentiate this again to get that $$\sum_{k=1}^{\infty}k^3 x^{k-1} = \dfrac1{(x-1)^2} + \dfrac6{(x-1)^3} + \dfrac6{(x-1)^4}$$ Hence, $$\sum_{k=1}^{\infty}k^3 x^{k} = \dfrac{x}{(x-1)^2} + \dfrac{6x}{(x-1)^3} + \dfrac{6x}{(x-1)^4} \in \mathcal{O}_x(1) \,\,\,\,\,\, \forall x \in (0,1)$$ Take $x= \dfrac12$ to get what you want.

Solution 2

Here is a hands-on 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/(1-2^{-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.

4,626

Jo Dane

Updated on January 30, 2020

Comments

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 big-oh, 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.