To prove that every integer n≥2 is a product of primes, if k+1=ab with 2≤ a,b≤ k, which hypothesis is used?

Exercise · ZW-STRONG-INDUCTION-004 · ★☆☆ Basic

To prove that every integer \(n\ge2\) is a product of primes, if \(k+1=ab\) with \(2\le a,b\le k\), which hypothesis is used?

Choose one option.

Show answer

D. \(P(a)\) and \(P(b)\) together

Explanation

The factors \(a\) and \(b\) are smaller than \(k+1\) but need not equal \(k\): the strong hypothesis on both is needed.

Study Discrete mathematics in ZWMath →

Review the concept: Strong induction

Strong induction proves \(P(n)\) for every \(n\ge n_0\): after checking the base case \(P(n_0)\), one proves \(P(k+1)\) assuming \(P(j)\) for all \(j\) with \(n_0\le j\le k\).

\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(n_0)\wedge\cdots\wedge P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]

To prove that every integer \(n\ge2\) is a product of primes, if \(k+1=ab\) with \(2\le a,b\le k\), which hypothesis is used?

Explanation

Review the concept: Strong induction

More practice problems: strong induction