0
$\begingroup$

I feel like this may be a dumb question, but I was wondering how to go about phrasing the answer for the following problem:


What is wrong with the following proof?

  1. For each $n \in \mathbb{Z}_{\geqslant 0}$, let $P(n)$ be the proposition "$2^n = 1$".
  2. (Base step) $P(0)$ is true because $2^0 = 1$.
  3. (Induction step)
    1. Let $k \in \mathbb{Z}_{\geqslant 0}$ such that $P(0), P(1), \ldots, P(k)$ are true, i.e., that $$2^0 = 2^1 = \cdots = 2^k = 1.$$
    2. Then, $$\begin{align} 2^{k + 1} &= \dfrac{2^k \times 2^k}{2^{k - 1}}\\ &= \dfrac{1 \times 1}{1}\\ &= 1. \end{align}$$
    3. Thus $P(k + 1)$ is true.
  4. Hence $\forall n \in \mathbb{Z}_{\geqslant 0}\, P(n)$ is true by strong mathematical induction.

Now I clearly understand that the proposition is false, but I'm not exactly sure how I should formally state this. Would it suffice to say that the premise of the induction step is false? If not, how else would I define this fallacy?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

The induction step does not work for $k=0$, since you use that $2^{k-1}=1$, which is not assumed at this step (you have nothing about $P(-1)$).

$\endgroup$
1
  • $\begingroup$ Ohh it's a lot simpler than I thought. Thank you so much :D $\endgroup$
    – Peter
    Sep 27, 2020 at 14:10
2
$\begingroup$

$2^{k-1}=1$ does not hold by induction hypothesis if $k=0$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .