What exactly is the 'induction trap' I've looked everywhere, and I've looked at a lot of examples. I don't quite understand what about the induction trap is so wrong. The most common example is the graph theory tree example (page 5 here: https://classes.soe.ucsc.edu/cmps102/Spring15/lect/1/ind-tantalo.pdf). Can anyone explain it?
 A: The problem is here "Add a new vertex and join it to $T$ with a new edge. The resulting graph has $n + 1$ vertices and $n$ edges." All you've shown here is that this new graph satisfies your desired conclusion. You have not shown this is true for any arbitrary graph on $n+1$ vertices. The problem in this step is that when you try to claim its true for any graph on $n+1$ vertices you are implicitly claiming that every tree can be constructed by adding vertices to a smaller tree. That is not a given (it does end up being true though). Normally with induction you really start with $n+1$ break it down to $n$ apply your induction hypothesis and go back up. If you choose to instead go directly up you need to be careful that this actually leads you to all possible cases above.
A: I've never heard the term "induction trap" but from what I can figure from the link is it is when instead of performing induction on a  k = n case you step down to an n-1 case and then go back up to the n case and show the n+1 case.
The problem is that the n-1 case may not have been valid.
The best example is the proof that in any group of horses, all horses in the group are the same color.
If n=1 then all horses in any group of 1 are the same color.  True.
Induction step:  Assume there is an n for which all n horses in any group of n are the same color.  Remove a horse so that you have n-1 horse. PROBLEM!  We never verified for the n = 0 case.  All zero horses are the same color but vacuously.  There is no single one color for them all to be.  From here on our proof is doomed.
OUR BIG INVALID STEP.  All the remaining n-1 horses are the same color as the removed horse.  NOT VERIFIED FOR n-1 = 0. It's only vacuously true. 
From here on our reasoning is sound but our premise is bad.  Add a new horse, we have n horses.  Any group of n horses must be the same color.  So the new horse must be the same color as the n-1 horses.  Add the original horse.  It's the same color as the n-1 horses and therefore as the new horse itself.  So all n+1 horses are the same color.   So any group of n+1 horses are the same color.
Had we started at n = 0 and initially stated "All 0 horses are the same color" we'd recognize that as true but from which any induction is impossible (as they are the same color vaccuously but it is not the case that they are a specific color).
