Proof by Induction: Number of bit strings of length $n$ starting with a 1 or ending with a 0 
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.
 A: 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$.
A: $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}$$
