Simplifying $\sum_{j=k}^{n}\binom{j}{k}/(2^{k-1})$

Question

While doing an exercise (computing an expected value), I encountered an expression that looks like this. Is there a simpler formula?

$$ \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} $$

If it wasn't for the denominator, I knew the solution.

Answer 1

Recall that

$$\sum_{j=0}^a\binom{j}{k} = \binom{a+1}{k+1}$$ Then: $$\sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} = \frac{1}{2^{k-1}}\left[\sum_{j=0}^n\binom{j}{k}-\sum_{j=0}^{k-1}\binom{j}{k}\right] = \frac{1}{2^{k-1}}\left[\binom{n+1}{k+1}-\binom{k}{k+1}\right] = $$

$$=\frac{1}{2^{k-1}}\binom{n+1}{k+1}$$

given that $$\binom{k}{k+1} = 0$$

Answer 2

$$\large\begin{align} \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} &=\frac 1{2^{k-1}}\sum_{j=k}^n \binom jk\\ &=\frac 1{2^{k-1}}\binom{n+1}{k+1}\qquad \blacksquare \end{align}$$

NB - the summation can be taken from $j=k$ instead of from $j=0$ because $\binom jk=0$ for $j<k$.