Consider the set of bitstrings $x\in\{0,1\}^{n+k}$ with $n$ zeros and $k$ ones with the additional condition that no ones are adjacent. (For $n=3$ and $k=2$, for example, the legal bitstrings are $00101$, $01001$, $01010$, $10001$, $10010$, and $10100$.) Prove by induction on $n$ that the number of such bitstrings is $\binom{n+1}k$.
I believe that the base case ends up being something like what I wrote below, and I want to use strong induction, but I am having a hard time figuring out, I suppose, what how to determine the number of valid bitstrings so that I can prove that it is equal to $\binom{n+1}k$.
HINT: If you must do it by induction, you can do a double induction on $k$ and $n$: for each $k$ prove the result for that $k$ by induction on $n$, assuming that it’s true for all smaller values of $k$.
Note that $\binom{n+1}k=\binom{n}k+\binom{n}{k-1}$. Try to see why the number of acceptable strings with $n+1$ zeroes and $k$ ones is the number with $n$ zeroes and $k$ ones plus the number with $n$ zeroes and $k-1$ ones; considering the last bit of an acceptable string of $n+1$ zeroes and $k$ ones may help.
Added:
Let $\Bbb N$ be the set of non-negative integers, and let $a(n,k)$ be the number of allowable strings with $n$ zeroes and $k$ ones; we want to show that $a(n,k)=\binom{n+1}k$ for all $n,k\in\Bbb N$. Because two independent integer variables are involved, we’ll do this as a double induction. For $k\in\Bbb N$ let $P(k)$ be the assertion that $a(n,k)=\binom{n+1}k$ for all $n\in\Bbb N$; we’ll prove the statements $P(k)$ by induction on $k$, and the proof of each $P(k)$ (except $P(0)$) will itself be a proof by induction on $n$.
To get started, we first prove $P(0)$, i.e., that $a(n,0)=\binom{n+1}0$ for each $n\in\Bbb N$. This is easy: for any $n\ge 0$ there is only one string of $n$ zeroes and no ones, and it is allowable, so $a(n,0)=1=\binom{n+1}0$ for each $n\in\Bbb N$.
For the induction step we want to show that $P(k)$ implies $P(k+1)$. That is, we want to show that if $a(n,k)=\binom{n+1}k$ for each $n\in\Bbb N$, then $a(n,k+1)=\binom{n+1}{k+1}$ for each $n\in\Bbb N$. We’ll do this by induction on $n$. To get the induction started, what is $a(0,k+1)$? It’s the number of allowable strings with no zeroes and $k+1$ ones. If $k=0$, there is exactly one such string, the string $1$, so $a(0,1)=1=\binom11$, as desired. And if $k>0$, then $k+1\ge 2$, and there are no such strings; thus, $a(0,k+1)=0=\binom1{k+1}$, again as desired. This takes care of the base case.
For the induction step suppose that $a(n,k+1)=\binom{n+1}{k+1}$; we want to show that $a(n+1,k+1)=\binom{n+2}{k+1}$. We’ll do this by dividing the allowable strings with $n+1$ zeroes and $k+1$ ones into two categories and counting the members of those categories separately. The first category consists of the allowable strings that have $n+1$ zeroes and $k+1$ ones and end in $0$. If you remove that final $0$, what’s left? What remains is an allowable string with $n$ zeroes and $k+1$ ones. Conversely, if you start with an allowable string with $n$ zeroes and $k+1$ ones and add a $0$ at the end of the string, you get an allowable string with $n+1$ zeroes and $k+1$ ones. Thus, there is a bijection between the set of allowable strings with $n+1$ zeroes and $k+1$ ones that end in $0$ and the set of allowable strings with $n$ zeroes and $k+1$ ones. There are $a(n,k+1)$ of the latter, and by the induction hypothesis $a(n,k+1)=\binom{n+1}{k+1}$, so
What about the allowable strings with $n+1$ zeroes and $k+1$ ones that end in $1$? Each of those strings must actually end in $01$, since an allowable string cannot end in $11$. What is left if we remove that final $01$? It must be an allowable string with $n$ zeroes and $k$ ones. Conversely, if we start with an allowable string with $n$ zeroes and $k$ ones, we can always add $01$ at the end to get an allowable string with $n+1$ zeroes and $k+1$ ones that ends in $1$. This means that there is a bijection between the set of allowable strings with $n+1$ zeroes and $k+1$ ones that end in $1$ and the set of allowable strings of $n$ zeroes and $k$ ones. There are $a(n,k)$ of the latter, and we’re assuming $P(k)$, so we know that $a(n,k)=\binom{n+1}k$. That is,
Every allowable string of $n+1$ zeroes and $k+1$ ones ends in either $0$ or $1$, and there is no overlap between these two categories, so
$$\begin{align*} a(n+1,k+1)&=a(n,k+1)+a(n,k)\\ &=\binom{n+1}{k+1}+\binom{n+1}k\\ &=\binom{n+2}{k+1}\;, \end{align*}$$
which is exactly what we wanted. It follows by induction that $a(n,k+1)=\binom{n+1}{k+1}$ for each $n\in\Bbb N$, and we have now proved $P(k+1)$, completing the induction step for the induction on $k$. Thus, we can now conclude that $P(k)$ holds for each $k\in\Bbb N$ and hence that $a(n,k)=\binom{n+1}k$ for all $k,n\in\Bbb N$.