Using induction to prove all numbers are prime or a product of primes Let $n$ and $d$ denote integers. We say that $d$ is a divisor of $n$ if $n = cd$ for some integer $c$. An
integer $n$ is called a prime if $n > 1$ and if the only positive divisors of $n$ are $1$ and $n$. Prove, by
induction, that every integer $n > 1$ is either a prime or a product of primes.
My try:
First, that there's nothing to prove because a number is always a prime or not, so do not what to think.
Step: 
$P(n): n$ is either a prime or a product of primes.
If n=2 then 2 is prime. 
$P(n): True$
I want to see $P(n) \rightarrow P(n+1)$
If $n$ is a prime then  $2$ is a divisor of $p+1$, then is a product of primes.
If $n$ is a product of primes... I can't say anything about $n+1$. 
Some help... please.
 A: This is a case where strong induction is needed, because a factorization of $n$ gives no information whatsoever on the factorization of $n+1$.
For the sake of brevity, I'll say that a number is a product of primes also when it is prime. Thus the statement is: “Every number $n\ge2$ is a product of primes”.
So the steps are


*

*Prove the base case, here $n=2$

*Prove that, if $n>2$ and every number $m$ with $2\le m<n$ is a product of primes, then also $n$ is a product of primes.
The base case is OK, as $2$ is prime.
Suppose $n>2$. If $n$ is prime, we're done. Otherwise $n=ab$, with $1<a<n$ and $1<b<n$. By the induction hypothesis, $a$ and $b$ are product of primes.
A: Strong induction:
Base case: $n=2$
$n$ has factors of 1,2 $n$ is prime:
Suppose for all $k\le n, k$ is either prime or can be represented as the product of a collection of prime factors.
We must show that either $n+1$ is prime or $n+1$ can be represented as the product of a collection of prime factors.
Suppose there are $2 \le c,d \le n$ such that $cd = n+1.$
In the case that n+1 is not prime. $c,d$ must either be prime or are the product of a set of prime factors.  $cd$ is the product of prime factors.
If $c,d$ do not exist then $n+1$ is prime.
$n+1$ is either prime or the product of prime factors.    
QED
A: Suppose that every integer $k$ such that $2\leq k\leq n$ is prime or a product of primes. This is the strong inductive hypothesis. You've already shown the base case. We show that $n+1$ is prime or a product of primes. If $n+1$ is prime we are done. Otherwise, write $n+1=ab$ where $2\leq a,b\leq n$ and use the inductive hypothesis.
