# Homework Assignment on Asymptotics

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!

-
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
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

Use can use $$\sum_{h=1}^n \frac{h}{2^h} \leq \sum_{h=1}^\infty \frac{h}{2^h} =2$$
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