0
$\begingroup$

I want to show that $f(n)=\Theta(g(n))$, where $$ f(n) = \sum_{k=1}^n k^2 2^k,\quad g(n) = n^2 2^n\,. $$

I know that for $f(n)=\Theta(g(n))$ means there exist positive constants $c_1$, $c_2$ and $n_0$ such that $0 \leq c_2 g(n) \leq f(n) \leq c_2 g(n)$ for all $n \geq n_0$.

Proving $f(n) \geq c_1 g(n)$ (for $c_1=1$) is trivial, how do I show $c_2g(n) \geq f(n)$?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Hint #1:

For all $1\leq k\leq n$, $k^2 2^k \leq n^2 2^k$.

Hint #2: $$ \sum_{k=1}^n n^2 2^k = n^2 \sum_{k=1}^n 2^k = n^2\cdot ?? $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .