Question

Show that the principle of mathematical induction and strong induction are equivalent; that is, each can be shown to be valid from the other.

Short answer

The principle of mathematical induction and strong induction are equivalent by showing that they are valid from the other.

Step-by-step solution

Significance of the induction

The induction is described as a process to prove a particular theorem or a statement. Induction consists of two types such as simple and strong induction.

Determination of the validity of the mathematical and strong induction

In the first part, it has been assumed that mathematical induction principle is valid. Here,$P\left(0\right)$ and also$P\left(k\right)\to P(k+1)$ implies that$P\left(n\right)$ holds true for the positive integers. Let$P\left(0\right)$ and alsorole="math" localid="1668559608622" $P\left(0{)}^{\wedge }P\right(1{)}^{\wedge }\dots P\left(k\right)\to P(k+1)$ holds true for the positive k integers $P\left(k\right)$. Let holds true.

Let it be assume, for contradiction, that$P(k+1)$ is not true. Let the smallest integer be i having$0<i<k$ which shows that$P\left(i\right)$ is not true. It is to be noted that$P\left(0\right),P\left(1\right),...,P(i-1)$ is true in whichrole="math" localid="1668559639847" $P\left(0{)}^{\wedge }P\right(1{)}^{\wedge }\dots P(i-1)\to P\left(i\right)$ is also true that states that$P\left(i\right)$ is true. As$P\left(i\right)$ is also false and true, a contradiction has been obtained in which the assumption $P(k+1)$is not true, is incorrect that shows that$P(k+1)$ is true.

$P\left(k\right)\to P(k+1)$holds true for the integers which are positive, as$P\left(0\right)$ also holds true. According to the mathematical induction principle,$P\left(n\right)$ is for the positive integers and the strong induction principle holds valid.

In the second part, it has been assumed that the mathematical induction principle is valid.$P\left(0\right)$ and$P\left(0{)}^{\wedge }P\right(1{)}^{\wedge }\dots P\left(k\right)\to P(k+1)$ for the positive integers which implies$P\left(n\right)$ holds for all positive integers.

Let$P\left(0\right)$ and$P\left(k\right)\to P(k+1)$ holds true for the positive k integers. Let$P\left(0\right),P\left(1\right),...,P\left(k\right)$ holds true. As$P\left(k\right)$ holds true,$P(k+1)$ also holds true as$P\left(k\right)\to P(k+1)$ holds true. It shows that$P\left(0{)}^{\wedge }P\right(1{)}^{\wedge }\dots P\left(k\right)\to P(k+1)$ holds true for the positivek integers as$P\left(0\right)$ also holds true. According to the strong induction$P\left(n\right)$ principle, holds true for the positive integers and also the mathematical induction principle is valid.

Thus, the principle of mathematical induction and strong induction are equivalent by showing that they are valid from the other.