What's wrong with this induction proof?

Question

Theorem: $n < 10^n$

For $P(0)$, $0 < 1$

Inductive Hypothesis: Assume $k < 10^k$

We must show $k+1 < 10^{k+1} $

By the inductive hypothesis, we know, $k < 10^k$

Plugging in $k + 1$ in place of $k$ for the inductive hypothesis, we get $k+1 < 10^{k+1} $

Which is what we are trying to prove. Thus, the statement is true.

Obviously this proof is flawed, but I cannot seem to articulate why. Is it simply because $k+1 \ne k$?

Answer 1

The issue is you cannot "Just plug it in" and think it works, you've already assumed your conclusion then while trying to prove it. That is no good.

To do it properly it would be

$$k+1<10^k+1<10^k\cdot 10=10^{k+1}$$

Answer 2

The mistake is in the line,

Plugging in $k + 1$ in place of $k$ for the inductive hypothesis, we get $k+1 < 10^{k+1} $

In applying the so-called Weak Mathematical Induction (which is what you have used in your 'proof') you need to prove $P(k+1)$ assuming $P(k)$. In your terminology you are free to plug in $k$ in place of $n$ in the statement $P(n)$. Loosely speaking if your statement is as follows, $$P(n):=n\ \text{satisfies the property}\ Q$$ then the Inductive Hypothesis says that you are free to "plug in" $k$ in place of $n$. In other words you may assume the following statement, $$P(k):=k\ \text{satisfies the property}\ Q$$But the key point here is that to "plug in" $k+1$ (for the same $k$ for which you assumed $P(k)$) you need to prove it. So the gap in your argument is that although you plugged in $k+1$ in place of $n$ (not $k$, which is fixed), you haven't justified why you can do so and this gap manifests itself (at least) in the line I quoted above.

Answer 3

Plugging in $k + 1$ in place of $k$ for the inductive hypothesis

The inductive hypothesis is that the proposition holds true for that particular $k\,$, not for any $\forall k\,$ (otherwise there would be nothing left to prove, would it). Therefore, you cannot "plug in" $k+1$ (or anything else, for that matter) in place of $k$.

Answer 4

The proof is wrong because you didn't prove anything, you are just stating clauses, namely $$k<10^k\text{ and }k+1<10^{k+1}$$ which may be true of false, you don't know beforehand.

What you have to do is to show the logical dependence

$$k<10^k\implies k+1<10^{k+1}$$ which is a very different matter.

Now if the clause is true for $k=0$ (by the base hypothesis), you get the following chain of implications:

$$0<10^0\implies 1<10^1\implies 2<10^2\implies 3<10^3\implies\cdots$$

Induction will perform an infinity of proofs "automatically".

---

Now, up to you. Can you show that

$$k<10k\implies k+1<10^{k+1}\ ?$$

$$k<10^k\implies k+1<10^k+1\implies k+1<10^k+1+(9\cdot10^k-1)=10^{k+1}.$$