I am self-teaching and am doing the now-famous Tao Analysis I exercise 2.2.5 which guides us to use weak induction to prove strong induction.
Many of the solutions on this site, and elsewhere, use then notion of a vacuously true base case for the simple induction.
My Quesion – how can weak induction proofs work when the base case is vacuously true?
Discussion
The falling dominoes analogy of weak induction has helped me better grasp induction.
The inductive step $P(n) \implies P(n+1)$ where the truth of a property about a natural number $n$ implies that property is also true for its successor $n+1$. This corresponds to the mechanism of one domino knocking over the next one.
The base case, corresponding to a first domino falling, makes sense when $P(a)$ can be shown to be true for some natural number $a$.
A vacuously true $P(a)$ doesn't tell us that the property $P$ holds for $a$. It just says the property isn't applicable. In my mind, this isn't sufficient for the domino to fall.
I have tried reading about vacuous truth and can only conclude they are assumed true because they can't be proved false. This seem insufficient to start the inductive dominoes falling.
Best Answer
You may want to expel from your mind the notion that vacuous truth is somehow different from any other kind of truth. Vacuously true statements are just like any other kind.*
[*Updated elaboration on this point]
In general let's define a "vacuously true statement" as a statement of the form $\forall x, P(x)\implies Q(x)$, where $P(x)$ happens to be always false for every $x$ in the domain of discussion.
The key observation is that like any other "for all" statement, it can be translated in terms of existence as $\neg (\exists x \, \neg (P(x)\implies Q(x))$, which further translates to $\neg (\exists x\, (P(x)\wedge \neg Q(x))$, or in words, "there is no $x$ for which $P$ holds and yet $Q$ fails."
In other words, every for-all statement, vacuous or no, is a statement about the nonexistence of counterexamples. Once you start thinking this way, vacuously true statements become a little less mysterious, as they are simply ones that have no counterexamples because $P$ never holds. The key point is that the reason there are no counterexamples is besides the point in a for-all statement - only the conclusion that there are none concerns us.
[Note that in the original post below, "$\forall k<n\, P(k) $" could be thought of as an abbreviation for "$\forall k\, (k<n\implies P(k) )$", and so in the case $n=0$, the implication $\forall k\, (k<0\implies P(k) )$ becomes vacuously true in the sense of the preceding paragraphs.]
Let’s consider the case of strong induction, which we want to prove from weak induction. That is, we are given a statement $P$ such that whenever $P(k)$ is true for all $k<n$, we have $P(n)$. We wish to show using weak induction that $P(n)$ holds for all $n$.
Then we indeed prove that the base case is true. This is based on vacuous truth, but so what? It is an absolutely true statement that we won't find counter-examples satisfying both $n<0$ and $P(n)$. Yes, you could call this vacuous, but it doesn't matter, because our premise, namely that for all $n$, we have the implication $$(\forall k<n\, P(k) )\implies P(n)\text{,}\tag{1}$$ has no special asterisk that says the left hand side of the implication can't be vacuously true. So since $\forall k<0\, P(k)$ is true, the implication (1) gives $P(0)$, and the base case is proved. The induction step I think you are already comfortable with.
Remark
Lest you think we are doing some trickery here and pulling the wool over your eyes, conjuring up something from nothing, let me help clarify that we are not. To see this, observe that whenever we apply strong induction to prove something, we must prove the implication (1), for every $n$, including $n=0$. In doing so, we will be forced to cook up a proof that effectively proves the base case (using whatever facts we have established in the given application).
For example, to prove that every positive integer is either $1$ or a product of primes, to apply strong induction you first would need to show the implication that
(here we are starting from $1$ instead of $0$, but the same principle applies.) Your proof of this fact in the case when $n=1$ would need to show
Luckily, while the left hand side of the implication is (vacuously) true, the right hand side is also true, so the implication holds. But in this step we aren't creating something from nothing, we are instead effectively proving the base case as we would in weak induction. In other words, the vacuous truth of the left hand side of the implication forces us to establish that the right hand side is true in the base case using already known facts.