0

I have a summation series of the form: n + (n-2^1) + (n - 2^2) + (n - 2^3) .... + (n - 2^l), where n is the total number of nodes in a tree, and l is the height of the tree. Is there a formula for this series?

John Doe
  • 3
  • Why are you using that variable for the height of the tree. It looks like a 1. – Asinomás Aug 13 '13 at 21:07
  • 1
    Sure. Note that it's $(l+1)\cdot n - \left(2^1 + 2^2 + 2^3 + \dotsb + 2^l\right)$, so you need only find a formula for the sum of the powers of $2$. $2^1 = 2$, $2^1 + 2^2 = 2+4 = 6$, $2^1+2^2+2^3 = 2+4+8 = 14$. Try a few more, look hard, you find $\sum_{k=1}^m 2^k = 2^{m+1} - 2$. – Daniel Fischer Aug 13 '13 at 21:07

1 Answers1

1

$$n + (n-2^1) + (n - 2^2) + (n - 2^3) .... + (n - 2^l)$$ $$(l+1)n -( 2^1 + 2^2 + 2^3 +\cdots + 2^l)$$ $$(l+1)n -2( 2^0 + 2^1 + 2^2 +\cdots + 2^{l-1})$$ $$(l+1)n -2( 2^{l}-1)$$

Tpofofn
  • 4,771