Solution: 2017 Fall Midterm - 7

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer. What does $$ \sum_{k=2}^{n} {{n}\choose{k}} \cdot 2^{n-k} $$ count?

(a)

The number of strings of length $n$, where each character is $a$ or $b$, that contain at least one $a$.

(b)

The number of strings of length $n$, where each character is $a$ or $b$, that contain at least 2 many $a$'s.

(c)

The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least one $a$.

(d)

The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least 2 many $a$'s.

$ \binom{n}{k} $ is taking k a’s while the rest are b’s or c’s

$ 2^{n-k} $ is taking the rest of the bits and making them b’s or c’s

Because we increment the value of k, we’re saying the following:

With this, we capture all the possibilities of having k a’s and the rest being b’s or c’s.