Answer:
Lets say that P(n) is true if n is a prime or a product of prime numbers. We want to show that P(n) is true for all n > 1.
The base case is n=2. P(2) is true because 2 is prime.
Now lets use the inductive hypothesis. Lets take a number n > 2, and we will assume that P(k) is true for any integer k such that 1 < k < n. We want to show that P(n) is true. We may assume that n is not prime, otherwise, P(n) would be trivially true. Since n is not prime, there exist positive integers a,b greater than 1 such that a*b = n. Note that 1 < a < n and 1 < b < n, thus P(a) and P(b) are true. Therefore there exists primes p1, ...., pj and pj+1, ..., pl such that
p1*p2*...*pj = a
pj+1*pj+2*...*pl = b
As a result
n = a*b = (p1*......*pj)*(pj+1*....*pl) = p1*....*pj*....pl
Since we could write n as a product of primes, then P(n) is also true. For strong induction, we conclude than P(n) is true for all integers greater than 1.
