Paragraph

Let's count ternary digit strings, that is, strings in which each digit can be 0, 1, or 2.

  1. How many ternary digit strings contain exactly \(n\) digits?

  2. How many ternary digit strings contain exactly \(n\) digits and \(n\) 2's.

  3. How many ternary digit strings contain exactly \(n\) digits and \(n-1\) 2's. (Hint: where can you put the non-2 digit, and then what could it be?)

  4. How many ternary digit strings contain exactly \(n\) digits and \(n-2\) 2's. (Hint: see previous hint)

  5. How many ternary digit strings contain exactly \(n\) digits and \(n-k\) 2's.

  6. How many ternary digit strings contain exactly \(n\) digits and no 2's. (Hint: what kind of a string is this?)

  7. Use the above parts to give a combinatorial proof for the identity

    \begin{equation*} {n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n\text{.} \end{equation*}
in-context