Strong Induction Base Case Is a base case needed ?
In response to many questions on this subject I offer the clarification below.
 A: The principle of strong induction follows from the consideration of a “well ordered set”.  Such a set has an order relation between its elements and satisfies a condition that any non-empty subset has a least element: note that as any set is a subset of itself this also implies the set itself has a least element. The natural numbers {0, 1, 2, ..} with the normal < relation are a well ordered set (with 0 as the least element) and I’ll confine the immediate discussion to them. 
Define an initial segment of n ∈ N as {m ∈ N: m < n}, and notate it as s(n). I.e. s(n)  is the set of all numbers less than n, Observe particularly that for 0 the initial segment is empty, BUT IT STILL EXISTS as an (empty) set, i.e. s(0)= {}.
Suppose that S is a subset of N with the property that for any n ∈ N then s(n) ⊂ S ⇒ n ∈ S, and remember that {} is a subset of every set so that s(0) IS A SUBSET OF S and by the property of S then 0 MUST BE IN S. The proof that S = N is easy: Let X = N\S, i.e. those elements of N not in S, then if X is not empty  it has a least element, say x, and since x ≠ 0  there are elements of N less than x, i.e. s(x), and they must all be in S (they are not in N\S because x is the least element of N\S).  So by the property of S, with s(x) ⊂ S then x ∈ S too, but this is a contradiction (we assumed x the smallest element in X, ie. not in S) and so N\S must be empty and therefore S = N.
So for a subset S of N with the property that for any n then s(n) ⊂ S ⇒ n ∈ S, we have S = N. 
To apply this to a proof by induction we take some proposition P which is a function of n and define S to be a subset of N for which P(n) is true. We require to prove that S = N so we have to establish that if P(m) is true for all m in s(n) then P(n) is true, which then translates to s(n) ⊂ S ⇒ n ∈ S and we can call on strong induction to say that S = N. 
So is a base case needed or not ? It doesn't have to be explicitly stated as a requirement because it is implied that 0 ∈ S as a consequence that {} ⊂ S. When it comes to a proof that the proposition P complies with s(n) ⊂ S ⇒ n ∈ S the “inductive” part of the proof will usually establish that P(n) is true based on P(m) being true for some NON EMPTY set {m ∈ N: m <= n} ⊂ S. It is very unlikely that this part of the proof will be able to establish that P(0) is true based on the fact that {} ⊂ S and so it will probably be necessary to separately prove that 0 ∈ S, i.e. that P(0) is true. There are also propositions which refer to expressions involving n-1, n-2, etc. In such cases again, the “inductive” part of the proof can only refer to values of n for which the rest of the expression is defined: If P(n) refers for example to n-2 then the inductive proof can only show  s(n) ⊂ S ⇒ n ∈ S for n >=2 (assuming that we are starting from 0), so P(1) and P(0) will have to be separately proved because s(0) ⊂ S (always) requires that 0 ∈ S and {0}  = S(1) ⊂ S requires that 1 ∈ S. Whether or not these cases are called “base cases” is semantic: fact is that they have to be proved and normally proved separately from the inductive part of the proof.
One way to get really confused on this subject is to omit the reference to initial segments and try and deal with it in terms of “sets of smaller numbers”. This leads to statements like “0 is an element of S because there are no numbers less than 0 (in N)” which is somehow sucked out of thin air. It also blurs the issue of why 0 will probably need to be treated as a “base case”, i.e. because its initial segment is empty.
A final point: any subset of N starting from some number n is also a well ordered set, so inductive proofs can equally be used for such sets (e.g. n! > 2^n for n> 3).
Edited 12 March 2015 to give an example:
The favourite example for strong induction is that all integers (> 1) can be expressed as a product of primes. This is true for 2 (base case): suppose true for all integers up to n, then either n + 1 is prime or consists of two factors which are < n and in which case n + 1 is the product of two sets of primes and so always n + 1 can be expressed as a product of primes. This proof actually uses the power of strong induction in factoring n + 1 in to ANY two numbers < n, not just relying on the truth of the proposition for n itself.
Why is a base case needed ? because of the statement suppose true for all integers up to n and > 1. In the case of 2, there are no integers > 1 up to 2. Does this fact prove anything about 2 being prime ? no. So we have to establish this separately (and very simply - 2 is prime). Now we know that for any integers > 1 (i.e. for numbers > 2 which have a non-empty set of smaller integers > 1, and for 2 itself) we have that if the statement is true for all integers up to n then it is true for n + 1.
Another take on this - causal and non-causal truth.
In following mathematical proofs the statement A ⇒ B is normally interpreted that the truth of B is derived from the truth of A, i.e. that the truth of A causes the truth of B. But that is more than what formal logic says. All that A ⇒ B means is that B is true whenever A is true. As an example of a "non-causal" relationship, we might (currently) say that "Barrack Obama is US President ⇒ Vladimir Putin is Russian President". These is no causal relationship between the two statements (we think), but if the LHS is true (it is) then the RHS is true (it is) so this is a valid statement in logic.
In the simplest form of the principle of strong induction we need to prove that if S is a subset of N then S = N provided for any n ∈ N then s(n) ⊂ S ⇒ n ∈ S - one thing to be proved, no mention of a base case. An inductive component of such a proof will derive the truth for n using the truth about elements of a non-empty initial segment of n. This will be a causal proof, i.e. the truth for n will be derived from the truth about its predecessors. But the initial segment of 0 is the empty set {}, and the empty set is a subset of every set so {} ⊂ S and we need to prove that 0 ∈ S. This part of the proof will almost certainly be non-causal, i.e. we know that {} ⊂ S and we need to establish that 0 ∈ S so that we can say that s(0) ⊂ S ⇒ 0 ∈ S: the LHS and RHS are both true, but without a causal relationship between them
This is how the need for a "base case" emerges even though there is no specific mention in it in the statement of strong induction.
