Proof by Induction: Number of bit strings of length $n$ starting with a 1 or ending with a 0

Question

We showed that the number of bitstrings of length $n$ that begin with a 1 or end with a 0 (or both) is $3 \cdot 2^{n−2}$. Sketch a proof by induction for this.

Would we prove this by manipulation? I'm totally lost.

Answer 1

All possible bitstrings of length $n$ can be expressed as set via a regular expression: $$ L_n = (0 \mid 1)^n $$ for $n \ge 2$ we can decompose this into four disjoint subsets $$ L_n = (0|1) L_{n-2} (0|1) = (0 L_{n-2} 0) \cup (0 L_{n-2} 1) \cup (1 L_{n-2} 0) \cup (1 L_{n-2} 1) $$ The feasible words are in $$ L = (0 L_{n-2} 0) \cup (1 L_{n-2} 0) \cup (1 L_{n-2} 1) \quad (*) $$ from this we can directly read $$ \lvert L \rvert = 3 \lvert L_{n-2} \rvert $$ where $$ \lvert L_{n-2} \rvert = 2^{n-2} $$ For $n = 1$ we have $L_1 = \{ 0, 1 \}$ and $L = L_1$, so $\lvert L \rvert = 2$.

For $n = 0$ we have $L_0 = \{ \epsilon \}$ and $L = \emptyset$, so $\lvert L \rvert = 0$.

This gives $$ \lvert L \rvert = \begin{cases} 0 & ;n = 0 \\ 2 & ;n = 1 \\ 3 \cdot 2^{n-2} & ;n \ge 2, n \in \mathbb{N} \end{cases} $$

Induction is not needed.

An inductive proof would build a chain of true implications from some start element $n_0$, where one proofs the truth of the proposition. Then under the assumption of the truth for one particular $n \ge n_0$ one has to show the truth for $n+1$ as well. Finally one invokes the principle of induction to claim the truth for all $n \ge n_0, n \in \mathbb{N}$.

In detail:

We choose $n_0 = 2$ and state $L_2 = \{ 00, 01, 10, 11 \}$ and $L = \{ 00, 10, 11 \}$. It is $\lvert L \rvert = 3$ and the proposition is true.

We now assume that the proposition is true for some $n \ge 2$. We further take an arbitrary bitstring of length $n$: $w \in L_n$. Then $w0$ is feasible, and there are $2^n$ of such words.

The other case is $w1$. This word is only feasible, if $w$ was feasible bitstring of length $n$, which started with $1$. We know there were $3 \cdot 2^{n-2}$ feasible bitstrings. From equation $(*)$ we know that $2/3$ of them start with $1$. So we have $$ 2^n + (2/3)\cdot 3\cdot 2^{n-2} = 2^n + 2^{n-1} = 2 \cdot 2^{n-1} + 2^{n-1} = 3\cdot 2^{n-1} = 3\cdot 2^{(n+1)-2} $$ feasible strings of length $n+1$, which is the proposition for $n+1$.

Answer 2

$2^{n-1}$ bitstrings of length $n$ start with $1$ (fix first position). Similarly, $2^{n-1}$ bitstrings of length $n$ end with $0$. We have double counted the case where $1$ and $0$ are fixed at first and last positions respectively. Number of such cases is $2^{n-2}$. Hence, $$2(2^{n-1}) - 2^{n-2} = 3\cdot 2^{n-2}$$