# Big theta proof

• Jan 20th 2013, 05:46 PM
Sneaky
Big theta proof
Hi,

I need some help with this big theta proof:

Show that f(n) = summation (from h=1 to n) of h3/2h is big theta(1).

What I got so far:

omega(g(1)) <= f(n) <= O(g(1))
c1g(1) <= f(n) <= c2g(1)

For f(n) <= O(1)
f(n) = summation (from h=1 to n) of h3/2h <= 1c2
f(n) = 1/2 + 8/4 + ... + n3/2n <= c2
1/2 <= c2 and 8/4 <= c2 ... and n3/2n <= c2

Since n3/2n is the biggest term in the summation, then showing n3/2n <= c2 is enough to show that f(n) <= O(1).
And here is where I get stuck, I'm not sure what to do next...
• Jan 20th 2013, 07:51 PM
johng
Re: Big theta proof
Your assertion that ${h^3\over 2^h}$ is increasing is unfortunately false. In fact the given sequence is decreasing for h > 5 -- examine the function $f(x)={x^3\over 2^x}$.

Entirely new direction: does $\sum^\infty_{h=1}{h^3\over 2^h}$ converge? If so, does this mean your partial sums are $\Theta(1)$?
• Jan 20th 2013, 08:06 PM
Sneaky
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?
• Jan 20th 2013, 08:31 PM
johng
Re: Big theta proof
Let $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 $S(n)$ is some finite value s -- you don't need to know specifically the value of s. So there is an $N$ such that for ${n\geq N}$, $s-1. So $c_1=s-1$ and $c_2=s+1$ satisfy the requirement of $\Theta$. Remember $\Theta$ requires the inequality only for all $n\geq N$; i.e. only for "large" values of n.
• Jan 20th 2013, 08:44 PM
Sneaky
Re: Big theta proof
But for this, don't you need to show that limit is a finite number? How can this be done?
• Jan 20th 2013, 10:34 PM
johng
Re: Big theta proof
When we say a series converges, we mean $\lim_{n\rightarrow \infty}S(n)=s$, s a (finite) real number. Remember the ratio test for convergence: $\lim_{h\rightarrow\infty}{(h+1)^3/2^{h+1}\over h^3/2^h}=1/2<1$, so the series converges.
• Jan 21st 2013, 06:46 PM
Sneaky
Re: Big theta proof
nevermind, I get the question now. thanks
• Jan 21st 2013, 08:38 PM
Sneaky
Re: Big theta proof
shouldn't it be s-1 <= s(n) <= s+1 instead of s-1 < s(n) < s+1 ?
• Jan 23rd 2013, 10:00 AM
johng
Re: Big theta proof
Yes and no; see the attachment:

Attachment 26679
• Jan 23rd 2013, 06:02 PM
Sneaky
Re: Big theta proof
I don't under stand the last two sentences.

If s(n) (- (s-1, s+1), how is it that s(n) (- [s-1, s+1] ?

Doesn't normal parenthesis like '(' and ')' mean, up to but not including?
• Jan 23rd 2013, 09:40 PM
johng
Re: Big theta proof
Surely you know $3<4$ implies $3\leq4$. More generally, $(0,4)\subset[0,4]$; i.e. if $0 then $0\leq x\leq4.$