Using Strong Induction The statement is: If $n$ is an integer with $n &gt; 1$, then $n$ has a prime factor. I know you have to use $P(k+1)$ but I'm not sure how to implement that into the proof. Is this even going in the right direction?
All $n &gt; 1$ are a factor of themselves, therefore all primes have a prime factor which is themselves.  If we assumed there was a number X that was the smallest number to have no prime factors, then it would not be able to prime and it would have to have at least one factor p, smaller than itself (otherwise it would be prime).  If p itself has a prime factor r, then r would also be a factor of X - since it can be seen that if X = qp, and q = rs, then  r divides into X sp times

so p can have no prime factors - but we said that X was the smallest number with no prime factors, and p is smaller than X, so by contradiction, X can not exist.
This is a perfect example of strong vs. weak induction.  We don't care in the slightest bit that $n+1$ is the number immediately after $n$.  We care only that $n+1$ is larger than $1....n$.

Base case: $n =2$.  $n = 2 $ has a prime factor because $2$ itself is prime.

Induction step:  Assume that every number from $2....n$ have prime factors.

$n+1$ has factors.  Because all numbers have factors.  $n+1$ has $1$ and $n+1$ as factors.  Does it have any others?

If not, then $n+1$ is prime and that is a prime factor.

Otherwise if $n+1$ has a factor $k$, $k \ne 1; k \ne n+1$ where $k|n+1$....

Well, here are some questions for you:

Is  $k &gt; n+1$? 

If not then ... what is it compared to $n+1$?
..... So what else can we assume about $k$?  ... because we are doing strong induction so we are making an assumption of what...?

So what does that tell us about $n+1$?

====

The trick is on weak induction we would assume the property is true for $n$ to get that it is true for $n+1$.

In this strong induction we are not doing that.  We are assuming it is true on some $k$ that is not $n$ and using that it is true on $k$, and therefore it is true on $n+1$.  We are using i) $k|n+1$ and $k &lt; n+1$.  The number $n$... is completely off the table and has nothing to do with anything.