Prove by induction that any natural number is even or odd.

(∀n∈ℕ) (2|n) ∨ (2∤n)

Base case #1: n = 1, and 2∤1, and is odd.
Base case #2: n = 2, and 2|2, and is odd.

Let x = 2n or x = 2n + 1 by the quotient remainder theorem, x ∈ ℤ

For the first base case (n=1): Let 2x+1 = n. Then, n+2 = 2x+1+2 = 2(x+1)+1, where 0 ≤ 1 < 2. Therefore, 1, 3, 5, ... are not divisible by two (odd) by induction.

For the second base case (n=2) Let 2x = n. Then, n+2 = 2x+2 = 2(x+1). Therefore, 2, 4, 6, ... are divisible by two (even) by induction.

Therefore, any natural number is either even or odd by induction. q.e.d.

1) Does this proof contain any logical fallacies?
2) Is it permissible in proof by inductions to have two base cases?

Thanks!

Proofs by induction work on well-ordered sets, and the set of positive even numbers and the set of positive odd numbers are both well-ordered.

Except in the second basis step, 2|2 so 2 is even.

One problem I do see is you have a statement of the form
∀r (r∨~r)
Making truth tables, you see this is always true.... so it's not the best symbolic form to state the proof in.

Since the Principle of Mathematical Induction is equivalent to the Well-Ordering Principle, we could use that.
Prove: All natural numbers are either odd or even.
Proof (by contradiction): Suppose the statement were false. That is assume there exists some natural number n such that n is not odd and n is not even.
We need to derive a contradiction. Consider the set
S = {x: x is not odd and x is not even}.
Clearly, S is non-empty (from the hypothesis). Then, by the Well-Ordering Principle, there exists a smallest element of the set S, call is n_0. Then n_0 = k+1 for some natural number k. Since n_0 is the smallest member of S, then k must not be in S. Thus k is either even or odd.
Case 1: k is even.
Then there exists some positive integer a such that k = 2a. But then
n_0 = 2a+1 ∉ S,
contradiction.