0

Let $n ≥ 0$ and $k ≥ 0$ be integers.

1) How many bitstrings of length $n + 1$ have exactly $k + 1$ many $1$s?

2) Let $i$ be an integer with $k ≤ i ≤ n$. What is the number of bitstrings of length $n + 1$ that have exactly $k + 1$ many $1$s and in which the rightmost $1$ is at position $i + 1$?

Use the above two results to prove that:

$\sum\limits_{i=k}^n\binom{i}{k}=\binom{n+1}{k+1}$

1) seems pretty straight forward but I'm not sure about 2 and the proof.. thanks for any help.

Peter Woolfitt
  • 21,114
saeid
  • 21

1 Answers1

1

The idea of part $2$ is the same as part $1$ except now you have a rightmost $1$ at position $i+1$. This may look confusing, but you can realize that this is equivalent to choosing a bitstring of length $i$ which has $k$ many $1$s in it. This is because all the other positions are accounted for - the $(i+1)$-th position must have a $1$ and all greater positions must have $0$s in them (since the $(i+1)$-th $1$ was the rightmost $1$).

So you get an answer for part $2$: The number of bitstrings of length $i$ with $k$ many $1$s.

For the proof (usually referred to as a combinatorial proof), all you have to do is argue that these are the same because they count the same object. Note that each bitstring of length $n+1$ with $k+1$ many $1$s falls into exactly one of the categories of the $(i+1)$-th digit being the rightmost $1$.

Peter Woolfitt
  • 21,114