Mathematical Induction Problem Fibonacci numbers

[issacnewton]

Homework Statement

Prove that the number of $n$ digit binary numbers that have no consecutive 1's is the Fibonacci number $F_{n+2}$. For example, for $n=2$ there are three such numbers $(00, 01, 10)$, and $3 = F_{2+2} = F_4$. Also, for $n=3$ there are five such numbers $(000, 001, 010, 100, 101)$, and $5 = F_{3+2} = F_5$.

Relevant Equations

Mathematical Induction and Fibonacci sequence.

I have already shown base case above for $n=2$. Let $k \geq 2$ be some arbitrary in $\mathbb{N}$. Suppose the statement is true for $k$. So, this means that, number of k-digit binary numbers that have no consecutive 1's is the Fibonacci number $F_{k+2}$. And I have to prove that number of (k+1)-digit binary numbers that have no consecutive 1's is the Fibonacci number $F_{k+3}$. Actually, I have no clue where to start on this after the base case. I need help. This problem could have easier solution using combinatorics but I need to use induction here.

Thanks

 

[fresh_42]

Whatever you do, you need to find a way to count the additional binary numbers that add up with every step of increasing the length by one. If $M(n)$ is the set of described binary numbers of length $n$ then we need to know that
$$
|M(n+1)|=|M(n)|+|M(n-1)| \text{ or } |M(n+1)\backslash M(n)|=|M(n+1)|-|M(n)|=|M(n-1)|
$$
The rest is covered by the induction hypothesis. But there is no way around counting (additional) strings.

 

[issacnewton]

Looking at the identities you have written, I think, we need to use strong induction here. Is that right ?

 

[fresh_42]

Looking at the identities you have written, I think, we need to use strong induction here. Is that right ?

Yes. If you look at the strings and in particular at the leading $1$ then the formula becomes apparent.

 

[docnet]

Sorry about my earlier post (which I deleted), it was a notational/grammatical mess and I hope no one saw it.

Define $S_k$ as the set of $k$-length 2-bit strings with no consecutive 1s, and $c(S_k)$ as the number of elements in that set.

For the base case, $S_0=\{\emptyset\}$ and $c(S_0)=1=F_{0+2}.$ $S_1=\{0,1\}$ and $c(S_1)=2=F_{1+2}$.

For the induction hypothesis, assume that for $2\leq j\leq k$, $c(S_j)=F_{j+2}=F_{j+1}+F_j$.

Any $k$-length string that ends with 0 can be extended to become two $(k+1)$-length strings that end with 0 and 1. Similarly a $k$-length string that ends with 1 can be extended to become one $(k+1)$-length string that ends with 0. (You can check that these two operations on $S_{k}$ give you all the elements in $S_{k+1}$, without repetitions). And so

\begin{align*}c(S_{k+1})=&2\cdot \text{the number of strings in }S_{k}\text{ that end with 0}\\
&+\text{the number of strings in }S_{k}\text{ that end with 1}.\end{align*}

And there exists a one-to-one correspondence between elements in $S_{k-1}$ and elements that end with 0 in $S_{k}$, and

$$c(S_{k-1})=\text{the number of strings in }S_{k}\text{ that end with 0}.$$

Which gives

$$\text{the number of strings in }S_{k}\text{ that end with 1}=c(S_k)-c(S_{k-1}).$$


Combining these results, we have
\begin{align*}c(S_{k+1})=&2\cdot c(S_k)- [c(S_k)-c(S_{k-1})]\\
=&c(S_k)+c(S_{k-1}).\end{align*}
Having proved that the numbers $c(S_k)$ follow the above recurrence, the rest goes as:
\begin{align*}
c(S_{k+1})=&c(S_k)+c(S_{k-1})\\
=&F_{k+2}+F_{(k-1)+2}\\
=& F_{k+2}+F_{k+1}\\
=&F_{k+3}\\
=&F_{(k+1)+2}\end{align*}
The second line comes by the induction hypothesis and the fourth line comes by the Fibonacci recurrence. Is this a valid proof?

 

[issacnewton]

Ok, here is my improved version. I am going to use strong induction here. Let $P(n)$ be the statement that number of n-digit binary numbers that have no consecutive 1's is the Fibonacci number $F_{n+2}$. Now consider the base case of $n=1$. Here for 1-digit binary numbers, we have possibilities of either $1$ or $0$. So, just two possibilities. Also, $F_{1+2} = F_3 = 2$. Hence $P(1)$ is true. Next, consider $n=2$. There are now three numbers possible $(00, 01, 10)$. Also, $F_{2+2} = F_4 = 3$. Hence $P(2)$ is also true.

Now, let $k \geqslant 2$ be arbitrary in $\mathbb{N}$. Assume that for $1 \leqslant m \leqslant k$, $P(m)$ is true. Now consider $P(k+1)$. We will construct (k+1)-digit binary numbers in the following way. Start with digit $0$. Apart from $0$, we have to fill $k$ places. Since $P(k)$ is true, there are $F_{k+2}$ possibilities here. So, we just append that to $0$, which is the beginning digit. So, there are $F_{k+2}$ $(k+1)$ digit binary numbers if the number is to start with digit $0$.

Next, we start with digit $1$. Since, there can not be two consecutive 1's, the following digit must be $0$. So, first two digits of the number are $10$. So, we have to fill remaining $(k+1 - 2) = k-1$ places. Since, $k \geqslant 2$, $k - 1 \geqslant 1$. So, using induction hypothesis, $P(k-1)$ is true. So, there are $F_{k-1 + 2} = F_{k+1}$ numbers possible. We append these numbers to the string $10$. So, we get $F_{k+1}$ $(k+1)$ digit binary numbers starting with digit $1$.

Since, a binary number can start with either $0$ or $1$, these are only possibilities. Hence, total number of $(k+1)$ digit binary numbers are

$$ F_{k+2} + F_{k+1} $$

Using the recurrence relation for the Fibonacci numbers, $F_{k+2} + F_{k+1} = F_{k + 3} = F_{(k+1) + 2}$. Hence $P(k+1)$ is true. So, using the principle of strong induction, $P(n)$ is true for all $n \in \mathbb{N}$.

Is this good enough ?

 

[PeroK]

Ok, here is my improved version. I am going to use strong induction here. Let $P(n)$ be the statement that number of n-digit binary numbers that have no consecutive 1's is the Fibonacci number $F_{n+2}$. Now consider the base case of $n=1$. Here for 1-digit binary numbers, we have possibilities of either $1$ or $0$. So, just two possibilities. Also, $F_{1+2} = F_3 = 2$. Hence $P(1)$ is true. Next, consider $n=2$. There are now three numbers possible $(00, 01, 10)$. Also, $F_{2+2} = F_4 = 3$. Hence $P(2)$ is also true.

Now, let $k \geqslant 2$ be arbitrary in $\mathbb{N}$. Assume that for $1 \leqslant m \leqslant k$, $P(m)$ is true. Now consider $P(k+1)$. We will construct (k+1)-digit binary numbers in the following way. Start with digit $0$. Apart from $0$, we have to fill $k$ places. Since $P(k)$ is true, there are $F_{k+2}$ possibilities here. So, we just append that to $0$, which is the beginning digit. So, there are $F_{k+2}$ $(k+1)$ digit binary numbers if the number is to start with digit $0$.

Next, we start with digit $1$. Since, there can not be two consecutive 1's, the following digit must be $0$. So, first two digits of the number are $10$. So, we have to fill remaining $(k+1 - 2) = k-1$ places. Since, $k \geqslant 2$, $k - 1 \geqslant 1$. So, using induction hypothesis, $P(k-1)$ is true. So, there are $F_{k-1 + 2} = F_{k+1}$ numbers possible. We append these numbers to the string $10$. So, we get $F_{k+1}$ $(k+1)$ digit binary numbers starting with digit $1$.

Since, a binary number can start with either $0$ or $1$, these are only possibilities. Hence, total number of $(k+1)$ digit binary numbers are

$$ F_{k+2} + F_{k+1} $$

Using the recurrence relation for the Fibonacci numbers, $F_{k+2} + F_{k+1} = F_{k + 3} = F_{(k+1) + 2}$. Hence $P(k+1)$ is true. So, using the principle of strong induction, $P(n)$ is true for all $n \in \mathbb{N}$.

Is this good enough ?

This is a good solution. But, you spend a lot of time talking about the trivial parts of the proof and hardly mention some key points. I would have done something like this.

A string of $k + 1$ digits must start with 0 or 1, so we consider these two mutually exclusive cases.

If the string starts with 0, then the number of ways of completing the string to avoid consecutive 1's is precisely the number of such strings of length $k$.

If the string starts with 1, then the second digit must be 0, and the number of ways of completing the string to avoid consecutive 1's is precisely the number of such strings of length $k-1$.

(Edit: used $P(k)$ instead of $N(k)$)
We have, therefore, $N(k+1) = N(k) + N(k-1)$.

That's the core of the proof and is much better isolated like this. You can take that final equation and wrap it up in an inductive argument.

In your proof the critical points are buried in trivial statements about the process of induction. In fact, if I was being really critical, I'm not sure you actually said any of this explicitly.

 

[issacnewton]

Well, I am just write a lot of words. Just want to make sure that I am as clear as possible. I will learn your brevity. But I did say everything which you wrote.

 

[docnet]

This is a good solution. But, you spend a lot of time talking about the trivial parts of the proof and hardly mention some key points. I would have done something like this.

A string of $k + 1$ digits must start with 0 or 1, so we consider these two mutually exclusive cases.

If the string starts with 0, then the number of ways of completing the string to avoid consecutive 1's is precisely the number of such strings of length $k$.

If the string starts with 1, then the second digit must be 0, and the number of ways of completing the string to avoid consecutive 1's is precisely the number of such strings of length $k-1$.

We have, therefore, $P(k+1) = P(k) + P(k-1)$.

That's the core of the proof and is much better isolated like this. You can take that final equation and wrap it up in an inductive argument.

In your proof the critical points are buried in trivial statements about the process of induction. In fact, if I was being really critical, I'm not sure you actually said any of this explicitly.

Genuine question: if $P(k)$ is a statement, what does it mean to write expressions such as $P(k) + P(k-1)$? Sorry if I'm slow to follow. Thanks.

 

[PeroK]

Genuine question: if $P(k)$ is a statement, is it okay to write expressions such as $P(k) + P(k-1)$?

I wrongly assumed that $P(k)$ was a number. It should be something like $N(k)$.

 

[docnet]

I wrongly assumed that $P(k)$ was a number. It should be something like $N(k)$.

Aha! That makes sense. thank you.

 

[PeroK]

Well, I am just write a lot of words. Just want to make sure that I am as clear as possible. I will learn your brevity. But I did say everything which you wrote.

It's not so much brevity as being explicit about the critical points. It's only brief because I didn't include the whole proof - only the critical calculation for the inductive step.

If my proof was wrong, it would be much easier to identify where and why it's wrong.

If your proof had a mistake, then it could take ages to figure it out.