Proving by induction, if the base case fails to meet the main condition, what do we do?

Question

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct.

I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$.

Unfortunately, this rule doesn't work with the number $0$, so what can I do, it's pretty obvious that when $n$ is $0$, $x$ is also $0$. The assigment requires me to use the basic induction logic:

$$ P(0) \land \forall n : (P(n) \Rightarrow P(n+1)) \Rightarrow \forall n : P(n)$$

Can I consider $P(0)$ a special case of the proof, and then prove everything from $1$ onwards? I think it could be possible, but is there any way I can modify $P$ to work with $0$, in this case it doesnt'?

Answer 1

If you want to prove something like $P(n)$ for all $n\in\mathbb{N}$ and it turns out that $P(n)$ fails in some cases, say $P(n)$ might be wrong if $n<k$, then you can always come up with a different statement $Q(n)$ which stands for "$P(n) \lor n < k$" and instead prove $\forall n \in \mathbb{N}: Q(n)$ by induction.

Now, it might seem like with this modification the base case $Q(0)$ suddenly becomes suspiciously easy, but this is only because the real complication is now in the inductive step where you have to take special care of the step from $Q(k-1)$ to $Q(k)$.

But this is only the technical justification for why induction also works if you start with $P(k)$ instead of $P(0)$. In practice you can treat, as you suggested, $P(k)$ as the base case and proceed as usual to prove $\forall n \in \mathbb{N}: (n \geq k \Rightarrow P(n))$.

Answer 2

You can use induction on any infinite sequence of natural numbers (or integers, or any countably infinite sequence at all).

Basic induction says if S is a set of natural numbers and 0 is in S and (s + 1) is in S whenever S is in S then S = N, the whole set of natural numbers.

This is then applied to an inductive proof by letting S be the set of numbers for which P(s) is true, where P is a proposition based on the number s. So if P(0) is true then 0 is in S and if P(s+1) is true whenever P(s) is true then s+1 is in s whenever s is in S and S = N and P(n) is true for all n in N.

Is now T is some countably infinite sequence of $t_0, t_1, ....$ let S be the set of numbers for which $P(t_s)$ is true. If $P(t_0)$ is true and $P(t_{s+1})$ is true whenever $P(t_s)$ is true, then S = N and P(t) is true for all of the sequence T.

In your case the sequence is simply the natural numbers starting from 1 instead of from 0.