Question: 2019 Winter Midterm - 13

Author: Michiel Smid

We consider binary $2 \times n$ matrices, i.e., matrices with 2 rows and $n$ columns, in which each entry is 0 or 1. A column in such a matrix is called a $1 \atop 1$-column, if both bits in the column are 1.
For any integer $n \geq 1$ and integer $k$ with $0 \leq k \leq n$, let $M(n,k)$ be the number of binary $2 \times n$ matrices

that do not contain any $1 \atop 1$-column, and
contain exactly $k$ many 1's.

Which of the following is true for all integers $n \geq 2$ and $k$ with $1 \leq k \leq n-1$?

(a)

$M(n,k) = M(n,k-1)\ +$$\ 2 \cdot M(n-1,k-1)$

(b)

$M(n,k) = M(n,k-1)\ +$$\ M(n-1,k-1)$

(c)

$M(n,k) = M(n-1,k)\ +$$\ 2 \cdot M(n-1,k-1)$

(d)

$M(n,k) = M(n-1,k)\ +$$\ M(n-1,k-1)$