What's the correct way of concluding an induction proof? I had to prove that for every set $s$, the number of subsets with odd cardinalities is $2^{n-1}$.
I concluded that this formula holds everytime $|s| \geq 1$ and then I used an inductive process to prove that my predicate $P(n) \Rightarrow P(n+1)$... 
However I am a bit confused on how to express this final conclusion.
I originally concluded that:
$[\forall n \in \mathbb{N}, (P(n) \wedge n \geq 1 \Rightarrow P(n+1))] \Rightarrow \forall n \in \mathbb{N},   P(n)$
But then my confusion arose because I thought it could be better concluded in this way:
$[\forall n \in \mathbb{N}, P(n) \Rightarrow P(n+1)] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \wedge P(n)$
But finally, an implication also made sense...
$[\forall n \in \mathbb{N}, P(n) \Rightarrow P(n+1)] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \Rightarrow P(n)$
or 
$[\forall n \in \mathbb{N}, (P(n) \wedge n \geq 1 \Rightarrow P(n+1))] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \Rightarrow P(n)$
Can you help me?
 A: What we are essentially looking for is a formulation of the principle of induction.
As you probably know, the principle of induction consists of:


*

*A base step: $P(0)$ holds (or $P(1)$, or $P(n_0)$ for some appropriate base value $n_0$ -- in this case, $n_0 = 1$);

*An inductive step: $P(n)$ implies $P(n+1)$ for all $n \ge n_0$;

*The conclusion that $\forall n \ge n_0: P(n)$.


The first two are the premises, and the latter is the conclusion. Thus a correct and precise formulation of the principle of induction in symbolic form would be:
$$\Big(P(n_0) \land \forall n: n \ge n_0 \land P(n) \implies P(n+1)\Big) \implies \forall n: n \ge n_0 \implies P(n)$$
Of course, when $n_0$ is the smallest value in $\Bbb N$ ($0$ or $1$, depending on your convention), the $n \ge n_0$ part can be done away with.

Now to your suggestions, if we take the point of view that $0 \notin \Bbb N$, they are all equivalent (can you see what goes wrong with several of them if $0 \in \Bbb N$?).
However, all of them miss the critical premise that $P(1)$ holds.
