Problem
A binary string of length $n$ is a sequence with $n$ terms, each of which is either a 0 or a 1. For example, displayed below are the 16 binary strings of length 4.
$$\begin{array}{llllllll}0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 \\ 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111\end{array}$$
A change in a binary string is an occurrence of two consecutive terms in the string that are different (that is, one is a 0 and the other is a 1). For example, in the binary string 1001, there are two changes: the 10 at the beginning and the 01 at the end. In the same arrangement that the strings are presented above, the number of changes in each of the sixteen strings of length 4 is as follows:
$$
\begin{array}{llllllll}
0 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\
1 & 2 & 3 & 2 & 1 & 2 & 1 & 0
\end{array}
$$
How many binary strings of length $n$ have exactly $k$ changes? Justify your answer.
(For $n=4$, there are 2 with zero changes, 6 with one change, 6 with two changes, and 2 with three changes.)
(Your answers should be expressed in terms of binomial coefficients, rather than in algebraic expressions involving $n$ and $k$.)