Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently did a homework assignment and got zero credit on a question. I would really like to know how to prove this question. I will show my solution and I would like to know what I did wrong and what I should have wrote.

Prove that $\sum_{h=1}^{n} \frac{h}{2^h} = O(1)$.
I tried proving this with induction.
Base Case: $P(1)$: in $\sum_{i=1}^n \frac{h}{2^h} = \frac{1}{2} \leq c$ as long as c $\geq \frac{1}{2}$.
Induction Step $P(n) \rightarrow P(n+1)$: Assume $P(n)$. Then we have: $$ \sum_{h=1}^{n+1} \frac{h}{2^h} = \sum_{h=1}^{n} \frac{h}{2^h} + \frac{h+1}{2^{h+1}} \\ = c + \frac{h+1}{2^{h+1}} \\ = c \cdot (1 + \frac{h+1}{c\cdot{2^{h+1}}}) \\ \leq c\cdot (1 + \frac{1}{2\cdot{c}}) \\ \leq c\cdot(1+1) \\ = c(2) \\ = 2 \quad (Let c = 1) \\ = O(1) $$ Therefore, by induction we can see that $\sum_{h=1}^{n} \frac{h}{2^h} = O(1)$. First of all please excuse the poor formatting in this question, I am still learning Latex. Second, looking at my solution I can see some of the sloppy mistakes I made but I am still unsure how to solve this problem since I did not get a single credit for this question. Any help would be greatly appreciate. Thank you!

share|improve this question
1  
To begin with, you do not state clearly any induction step P(n). Which one do you consider? –  Did Oct 16 '12 at 15:49
1  
Your strategy is very deeply flawed because you need to prove that the same constant $c$ works for all $n$. If you use the same induction you could "prove" $\sum_{h=1}^n 1 = O(1)$ which is patently false. –  Erick Wong Oct 16 '12 at 15:53
    
What do you mean @did... I'm making the assumption that P(n) means that $\sum_{h=1}^{n} \frac{h}{2^h} = O(1) or \leq{c}$. –  InsigMath Oct 16 '12 at 16:01
    
@InsigMath What did is hinting at is that you are not very specific about what $c$ is. In your induction step you assume $c=1$ to prove that $c=2$. Not much of a constant is it? –  Erick Wong Oct 16 '12 at 16:20
    
Oh... I see what you mean. Yes, that is a pretty big problem. So, did I go about this completely, wrong then. @Fabian suggested using the identity $\sum_{h=1}^n \frac{h}{2^h} \leq \sum_{h=1}^{\infty} \frac{h}{2^h} = 2$. Would this have been a better way to prove this? I just really want to know how to solve this. –  InsigMath Oct 16 '12 at 16:29

1 Answer 1

up vote 0 down vote accepted

Use can use $$\sum_{h=1}^n \frac{h}{2^h} \leq \sum_{h=1}^\infty \frac{h}{2^h} =2$$

share|improve this answer
    
Does this mean that my approach by induction was completely flawed and this would have been the only sensible way of doing it? Thank you for this though I did not think of using a property like that. –  InsigMath Oct 16 '12 at 16:09
    
You can do also with induction, but then you have to take care that the constant does not change with $n$ (as was noted in the comments above). –  Fabian Oct 16 '12 at 21:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.