What's an induction problem that will be hard to answer with "backwards reasoning?"

Solution 1:

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}$.

Solution 2:

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).