When proving a statement by induction, how do we know which case is the valid 'base'? For example proving 2^n < n!, 4 is the 'base' that works for this exercise, then starting from there we prove p + 1 considering p has to be at least 4 and we have our result. However, I believe determining the first valid value without a previous proof is kind of odd.
The question is, how?
I don't want to upload my homework with assumptions justified like "it's obvious just try using 0,1,2,3 and see that it doesn't work".

The base case is usually so trivial that it is either obvious or can be immediately calculated without difficulty.  However, in a case such as yours where the first values do not work, one would usually proceed to show that there are a finite number of cases where the relation is not true, and then proceed to perform induction on the first (few) cases that do work.
For instance, in number theory the primes 2 and 3 are often exceptions to a relationship (because one is the only even prime, and they are the only consecutive primes), so $p \ge 5$ or $p \gt 5$ are common caveats.
