[proofplan] We count cd-monomials by viewing them as finite words in the alphabet $\{c,d\}$ with weighted degree given by $\deg c=1$ and $\deg d=2$. The base cases are the empty word in degree $0$ and the single word $c$ in degree $1$. For $n\ge 2$, every word of degree $n$ begins either with $c$ or with $d$, and deleting that first letter gives a bijection with words of degree $n-1$ or $n-2$, respectively. This gives the Fibonacci recurrence with the required shifted initial values. [/proofplan] [step:Verify the initial degrees] By convention, $M_0$ contains exactly the empty monomial, so $|M_0|=1$. A monomial of total degree $1$ cannot contain $d$, since $\deg d=2$, and must therefore be the one-letter monomial $c$. Hence $|M_1|=1$. Since $F_1=1$ and $F_2=1$, the desired formula holds for $n=0$ and $n=1$. [/step] [step:Partition positive-degree monomials by their first letter] Assume $n\ge 2$. Define $C_n\subset M_n$ to be the set of monomials in $M_n$ whose first letter is $c$, and define $D_n\subset M_n$ to be the set of monomials in $M_n$ whose first letter is $d$. Every nonempty word in the alphabet $\{c,d\}$ has first letter either $c$ or $d$, and these alternatives are mutually exclusive. Since every element of $M_n$ is nonempty for $n\ge 1$, we have a disjoint union $M_n=C_n\sqcup D_n$. [guided] We separate the words by their first letter because the first letter has a fixed contribution to the total degree. Let $C_n$ denote the set of degree-$n$ words beginning with $c$, and let $D_n$ denote the set of degree-$n$ words beginning with $d$. These two sets are disjoint: a word cannot have both $c$ and $d$ as its first letter. They also cover $M_n$ because $n\ge 2$ implies every word of total degree $n$ is nonempty, and every nonempty word over the alphabet $\{c,d\}$ has exactly one first letter. Therefore $M_n=C_n\sqcup D_n$. This disjoint partition is what allows us to add cardinalities later without double-counting. [/guided] [/step] [step:Delete the first letter to obtain the Fibonacci recurrence] Define $\alpha_n:C_n\to M_{n-1}$ by sending a monomial beginning with $c$ to the monomial obtained by deleting that first $c$. This map is bijective: its inverse sends $u\in M_{n-1}$ to the monomial $cu$, whose total degree is $1+(n-1)=n$. Define $\beta_n:D_n\to M_{n-2}$ by sending a monomial beginning with $d$ to the monomial obtained by deleting that first $d$. This map is bijective: its inverse sends $v\in M_{n-2}$ to the monomial $dv$, whose total degree is $2+(n-2)=n$. Thus $|C_n|=|M_{n-1}|$ and $|D_n|=|M_{n-2}|$. Using the disjoint union from the previous step, we obtain $|M_n|=|M_{n-1}|+|M_{n-2}|$. [/step] [step:Identify the resulting sequence with the shifted Fibonacci sequence] Define $a_n=|M_n|$ for every nonnegative integer $n$. The preceding steps give $a_0=1$ and $a_1=1$, while for every $n\ge 2$, $a_n=a_{n-1}+a_{n-2}$. The shifted Fibonacci sequence $b_n=F_{n+1}$ satisfies the same initial values, namely $b_0=F_1=1$ and $b_1=F_2=1$. For $n\ge 2$, the Fibonacci recurrence gives $b_n=F_{n+1}=F_n+F_{n-1}=b_{n-1}+b_{n-2}$. Therefore the two sequences agree by induction on $n$, and hence $|M_n|=F_{n+1}$ for every nonnegative integer $n$. [/step]