6
$\begingroup$

What is wrong with this "proof" by strong induction?

"Theorem": For every non-negative integer $n, 5n = 0$.
Basis Step: $5(0) = 0$
Inductive Step: Suppose that $5j = 0$ for all non-negative integers j with $0 \le j \le k$. Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$. By the inductive hypothesis, $5(k + 1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.$

My initial thought is that strong induction used variables less than $k$ and greater than $k$. $k-1$ is shown in forms of $i$ and $j$ but no $k+1$ is used.

$\endgroup$
8
$\begingroup$

Hint: Try the inductive step with $k = 0$.

$\endgroup$
  • $\begingroup$ Sorry its not ringing any bells. Only thing I can think of with this hint is that 5(k)=0. $\endgroup$ – Extreme112 Nov 3 '14 at 5:05
  • 8
    $\begingroup$ If $k = 0$, then $k+1 = 1$. Can you find $i,j < 1$ with $i+j = 1$? $\endgroup$ – André 3000 Nov 3 '14 at 5:57
0
$\begingroup$

Strong induction would require you to show two base cases for this proof ($n = 0$ and $n = 1$).

Think about it: It is only guaranteed from the base case that the statement holds for numbers $k$ so that $0 \leq k \leq 0$. The proof takes two numbers $i,j$ with $0 \leq i,j \leq 0$ to proceed with induction beyond this point. The problem lies in the fact that $i$ and $j$ then clearly must both be $0$. The proof wants induction to proceed beyond this point by having them add up to the next value (i.e. $1$). This clearly is not possible.

$\endgroup$
  • 1
    $\begingroup$ "Strong induction would require you to show two base cases for this proof ($n=0$ and $n=1$)." seems a bit misleading. The reason why one base case is not enough here is that this particular inductive step given in the "proof" does not work with $k=0$, not some intrinsic property of strong induction. $\endgroup$ – JiK Nov 3 '14 at 9:43
  • $\begingroup$ I said "for this proof". I didn't mean to make it sound too general. I was just trying to show why this specific proof required two. $\endgroup$ – user134593 Nov 3 '14 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.