What's an induction problem that will be hard to answer with "backwards reasoning?" I'm currently the teaching assistant for a course that serves as an introduction to rigorous proofs, and I've noticed some of my students have a tendency to try and use a sort of "backwards reasoning" on induction problems. Specifically, if they were asked to prove something like $n! > n^2$ for $n \geq 4$, for the inductive step they will start by writing the very inequality they want to prove:
$$ (n+1)! > (n+1)^2.$$
It's not just a case of assuming the conclusion however, because they'll then manipulate this inequality until they reach some new inequality they know is true, a la
\begin{align}
(n+1)n! &> (n+1)(n+1)\\
n! &> (n+1)
\end{align}
And then they'd say something like $n! > n^2 > n+1$, with this last inequality being something they'd already proved.
The problem then is that it's clear from looking at their work that many of them are getting tripped up by this method. Further, I doubt that most of them realize that this only works because each step in the chain of reasoning is reversible (at the very least, none of them made it explicit that they were relying on this fact).
I'd like to convince them that if they want to use this method, they need to be very careful. It would help emphasize my point if I could present an induction problem that would be difficult to answer using this method. In particular, I've been trying to think of a way to force them to use a step that is not reversible, so that this backwards reasoning leads to stating something that does not follow from their previous statement. Currently I'm messing around with things like $z^2 > 0$ followed by $z > 0$, but haven't found a problem that I feel is adequate yet. Any thoughts?
 A: Here is a problem which I believe to be difficult to solve by "backwards reasoning".
Problem: Show that every positive rational number can be written as a quotient of products of factorials of (not
necessarily distinct) primes. For example,
$\frac{10}{9} = \frac{2! \cdot 5!}{3! \cdot 3!\cdot 3!}$.
Solution: We will prove this for any rational number $\frac{a}{b}$ by induction on the largest prime divisor of a or b. In the base case a=b=1 and $\frac{a}{b} =  \frac{2!}{2!}$.
Now suppose that a and b have no common prime divisors and let p be the largest prime divisor of either a or b. WLOG we may assume p|a for otherwise we can take the reciprocal, apply this argument, and then take the reciprocal again.
Since p|a we have $\frac{a}{b} = \frac{(p!)^ra'}{(p-1)!^rb}$ such that a' and b have prime divisors strictly smaller than p. 
By induction $\frac{a'}{(p-1)!^rb}$ can be written as a quotient of factorials of primes. Multiplying this representation by (p!)^r gives the desired representation of $\frac{a}{b}$.
A: To show them that backwards reasoning is wrong, you could do something like "Claim: 1=2, Proof: 1=2 -> 1*0=2*0 -> 0=0 which is true so we are done."
If you want to show them something where starting with what you are proving is the wrong technique, maybe try something where you reduce it to a previous case. For instance, you can prove that every integer n>1 has a prime divisor (although that is strong induction).
