¿Cuántas cadenas de bits de longitud k tienen más de un 1?

Question

La pregunta parece bastante sencilla, pero no consigo obtener una fórmula cerrada.

Ej. para k=2 es 1 (11), para k=3 es 4 (111,101,110,011)

Pensé que tal vez podría ser $\frac{1}{2} \cdot 2^k $ pero no sé cómo probarlo.

Gracias por su ayuda.

Answer 1

Es $2^k$ menos el número de cadenas sin $1$ s o sólo uno $1$ .

Hay una cadena sin $1$ s: el que tiene todos ceros.

Hay $k$ cadenas con una sola $1$ : $1$ situado en el $i$ ón, con $1 \leq i \leq k$ y el resto ceros.

Así que.., $f(k) = 2^k - k - 1.$