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³/2^h is big theta(1).

What I got so far:

omega(g(1)) <= f(n) <= O(g(1))
c₁g(1) <= f(n) <= c₂g(1)

For f(n) <= O(1)
f(n) = summation (from h=1 to n) of h³/2^h <= 1c₂
f(n) = 1/2 + 8/4 + ... + n³/2ⁿ <= c₂
1/2 <= c₂ and 8/4 <= c₂ ... and n³/2ⁿ <= c₂

Since n³/2ⁿ is the biggest term in the summation, then showing n³/2ⁿ <= c₂ is enough to show that f(n) <= O(1).
And here is where I get stuck, I'm not sure what to do next...

Your assertion that is increasing is unfortunately false. In fact the given sequence is decreasing for h > 5 -- examine the function .

Entirely new direction: does converge? If so, does this mean your partial sums are ?

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?

Let . Then to say the series converges is to say the limit as n approaches infinity of is some finite value s -- you don't need to know specifically the value of s. So there is an such that for , . So and satisfy the requirement of . Remember requires the inequality only for all ; i.e. only for "large" values of n.

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

When we say a series converges, we mean , s a (finite) real number. Remember the ratio test for convergence: , so the series converges.

nevermind, I get the question now. thanks

shouldn't it be s-1 <= s(n) <= s+1 instead of s-1 < s(n) < s+1 ?

Yes and no; see the attachment:

Attachment 26679

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?

Surely you know implies . More generally, ; i.e. if then