Locating the error in a fallacious proof

Find the error in the following ``proof by induction'' of the statement: for all $n \geqslant 1$ the inequality $3^{n}>3(n+1)+1$ holds.

Suppose that for some $k \geqslant 1$ the inequality holds, that is $3^{k}>3(k+1)+1$; denote this inequality by $(*)$. Let us prove that it also holds for $n=k+1$, that is $3^{k+1}>3(k+2)+1$. To this end, note that for any $k \geqslant 1$ the inequality $2 \cdot 3^{k}>3$ holds. Adding its left- and right-hand sides to the corresponding sides of inequality $(*)$, we get $3^{k}+2 \cdot 3^{k}>3(k+1)+1+3$, or $3^{k+1}>3(k+2)+1$, as required.

Determine for which $n$ the inequality $3^{n}>3(n+1)+1$ actually holds.

Find the error in the following ``proof by induction'' of the statement: in every herd of $n$ cows, all the animals are the same color.

Base case: if $n=1$, the herd consists of a single cow, so all the cows are the same color. Inductive step: suppose the statement has been proved for $n$. Consider a herd of $n+1>1$ cows. Remove a cow $x$ from this herd; by the induction hypothesis all the remaining $n$ cows are the same color. Remove a different cow $y$ from this herd; by the induction hypothesis all the remaining $n$ cows are again the same color. We then get that the colors of the cows $x$ and $y$ coincide with the colors of all the other cows, so all the cows in the herd are the same color.

Find the error in the following proof that $2=1$. Consider the equation $a=b$. Multiply both sides by $a$ to obtain $a^{2}=a b$. Subtract $b^{2}$ from both sides to get $a^{2}-b^{2}=a b-b^{2}$. Now factor each side, $(a+b)(a-b)=b(a-b)$, and divide each side by $(a-b)$ to get $a+b=b$. Finally, let $a$ and $b$ equal 1, which shows that $2=1$.

Find the error in the following proof that all horses are the same color. Claim: In any set of $h$ horses, all horses are the same color. Proof: By induction on $h$. Basis: For $h=1$. In any set containing just one horse, all horses clearly are the same color. Induction step: For $k \geq 1$, assume that the claim is true for $h=k$ and prove that it is true for $h=k+1$. Take any set $H$ of $k+1$ horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set $H_{1}$ with just $k$ horses. By the induction hypothesis, all the horses in $H_{1}$ are the same color. Now replace the removed horse and remove a different one to obtain the set $H_{2}$. By the same argument, all the horses in $H_{2}$ are the same color. Therefore, all the horses in $H$ must be the same color, and the proof is complete.

Describe the error in the following "proof" that $0^{*} 1^{*}$ is not a regular language. (An error must exist because $0^{*} 1^{*}$ is regular.) The proof is by contradiction. Assume that $0^{*} 1^{*}$ is regular. Let $p$ be the pumping length for $0^{*} 1^{*}$ given by the pumping lemma. Choose $s$ to be the string $0^{p} 1^{p}$. You know that $s$ is a member of $0^{*} 1^{*}$, but Example 1.73 shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*} 1^{*}$ is not regular.