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!

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