
Big theta proof
Hi,
I need some help with this big theta proof:
Show that f(n) = summation (from h=1 to n) of h^{3}/2^{h} is big theta(1).
What I got so far:
omega(g(1)) <= f(n) <= O(g(1))
c_{1}g(1) <= f(n) <= c_{2}g(1)
For f(n) <= O(1)
f(n) = summation (from h=1 to n) of h^{3}/2^{h} <= 1c_{2}
f(n) = 1/2 + 8/4 + ... + n^{3}/2^{n} <= c_{2}
1/2 <= c_{2 }and 8/4 <= c_{2 } ... and n^{3}/2^{n} <= c_{2 }
Since n^{3}/2^{n} is the biggest term in the summation, then showing n^{3}/2^{n} <= c_{2} is enough to show that f(n) <= O(1).
And here is where I get stuck, I'm not sure what to do next...

Re: Big theta proof
Your assertion that $\displaystyle {h^3\over 2^h}$ is increasing is unfortunately false. In fact the given sequence is decreasing for h > 5  examine the function $\displaystyle f(x)={x^3\over 2^x}$.
Entirely new direction: does $\displaystyle \sum^\infty_{h=1}{h^3\over 2^h}$ converge? If so, does this mean your partial sums are $\displaystyle \Theta(1)$?

Re: Big theta proof
Oh ok, I see that when h > 5, it decreases. It then converges at 0 when h > infinity.
But how can I evaluate the limit of the summation at h = infinity?

Re: Big theta proof
Let $\displaystyle S(n)=\sum^n_{h=1}{{h^3\over 2^h}$. Then to say the series converges is to say the limit as n approaches infinity of $\displaystyle S(n)$ is some finite value s  you don't need to know specifically the value of s. So there is an $\displaystyle N$ such that for $\displaystyle {n\geq N}$, $\displaystyle s1<S(n)<s+1$. So $\displaystyle c_1=s1$ and $\displaystyle c_2=s+1$ satisfy the requirement of $\displaystyle \Theta$. Remember $\displaystyle \Theta$ requires the inequality only for all $\displaystyle n\geq N$; i.e. only for "large" values of n.

Re: Big theta proof
But for this, don't you need to show that limit is a finite number? How can this be done?

Re: Big theta proof
When we say a series converges, we mean $\displaystyle \lim_{n\rightarrow \infty}S(n)=s$, s a (finite) real number. Remember the ratio test for convergence: $\displaystyle \lim_{h\rightarrow\infty}{(h+1)^3/2^{h+1}\over h^3/2^h}=1/2<1$, so the series converges.

Re: Big theta proof
nevermind, I get the question now. thanks

Re: Big theta proof
shouldn't it be s1 <= s(n) <= s+1 instead of s1 < s(n) < s+1 ?

1 Attachment(s)
Re: Big theta proof
Yes and no; see the attachment:
Attachment 26679

Re: Big theta proof
I don't under stand the last two sentences.
If s(n) ( (s1, s+1), how is it that s(n) ( [s1, s+1] ?
Doesn't normal parenthesis like '(' and ')' mean, up to but not including?

Re: Big theta proof
Surely you know $\displaystyle 3<4$ implies $\displaystyle 3\leq4$. More generally, $\displaystyle (0,4)\subset[0,4]$; i.e. if $\displaystyle 0<x<4$ then $\displaystyle 0\leq x\leq4.$