Question

What is wrong with this “proof” by strong induction? “Theorem” For every nonnegative integer n, 5 n =0 .

Basis Step: 5.0=0 .

Inductive Step: Suppose that 5j=0 for all nonnegative integers j with $\mathbf{0}\mathbf{\le }\mathbf{j}\mathbf{\le }\mathbf{k}$. Write $\mathbf{k}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{i}\mathbf{+}\mathbf{j}$, where i and j are natural numbers less than k+1 . By the inductive hypothesis,$\mathbf{5}\mathbf{(}\mathbf{k}\mathbf{+1)=5(}\mathbf{i}\mathbf{+}\mathbf{j}\mathbf{)=5}\mathbf{i}\mathbf{+5}\mathbf{j}\mathbf{=0+0=0}$ .

Short answer

The wrong is the assumption that each and every integer which are positive such as$k+1$ can also be written as the sum of the natural numbers which are lesser than$k+1$ .

Step-by-step solution

Significance of the induction

The strong induction is described as a technique different from the simple induction in order to prove a particular theorem and statement. The strong induction takes less time compared to the simple induction while proving a theorem or statement.

Determination of the problems while proof by strong induction

In the step of induction, it has been assumed that the positive integers$k+1$ in which$k+1\ge 1$ as$k\ge 0$ is to be written as it is the sum of the two natural number which are less than $k+1$. Hence, in the case of $k+1=1$, the equation does not hold true as 1 is not to be written as the sum of the two natural numbers which are smaller than the number 1 .

Thus, the wrong is the assumption that each and every integer which are positive such as$k+1$ can also be written as the sum of the natural numbers which are lesser than$k+1$ .