0
$\begingroup$

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!

  • 1
    To begin with, you do not state clearly any induction step P(n). Which one do you consider?2012-10-16
  • 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.2012-10-16
  • 0
    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}$.2012-10-16
  • 0
    @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?2012-10-16
  • 0
    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.2012-10-16
  • 0
    @InsigMath Yes, it is usually impractical to prove $O(1)$ upper bounds by induction on $n$. One typically needs to replace the $O(1)$ hypothesis with a RHS that depends on $n$: often this is harder than finding a direct inequality.2012-10-16

1 Answers 1

0

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

  • 0
    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.2012-10-16
  • 0
    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).2012-10-16