Average length of a bitstring

Question

I am trying to compute the average length of a bit string from all bit strings of $\{0,1\}^n$. By length n I mean a bit string of length n where the most significant bit is 1. I know there is $2^0$ strings of length 1, $2^1$ strings of length 2 ... $2^{n-1}$ strings of length n.

So the average length over all strings can be computed as the # of strings of lenght n times n, over the total # of strings in $\{0,1\}^n$.

$\frac{\sum_{i=0}^{n} 2^{i}(i +1) }{2^n}$

I feel that this sum should be equal to (n - 1). However I can not simplify this sum into an expression.

Any ideas how to simplify this sum or maybe a different approach to computing the average length of all bitstrings.

Answer 1

The result should be $2n+2^{-n}$.

$\sum_{i=0}^n 2^i \cdot (i+1)=\sum_{i=0}^n i\cdot 2^i + \sum_{i=0}^n 2^i$, where the right summand is just the geometric sum. The left one is $\sum_{i=0}^n \sum_{j=i}^n 2^j$ and now you have a sum of geometric sums. And so on.

Does that help?

Answer 2

Let $$ f(x)=\sum_{i=0}^{n-1}x^i(i+1) $$ Note that f(x)=g'(x) where $$ g(x)=\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x}$$ (this is a sum of geometric series). Take the derivative g'(2) to obtain the sum $$\sum_{i=0}^{n-1}2^i(i+1)$$ and divide the result by 2^n.