# Induction proofs for subsets of integers

I know that induction can be used to prove that certain results hold true for all integers, all positive integers, all negative integers, all rational numbers and so on. What I'm noticing from listing all those sets down is that induction seems to work for proving results are true for countably infinite sets? Is that an accurate observation.

Getting down to the point, this question is specifically about proving results by induction for positive even numbers, another countably infinite set. (the bijection $f(n) = 2n$ is enough to see this).

To prove a proposition $P$ is true for all positive even numbers, would I need to assume a base case of $n=0, 2, \text{etc}\ldots$ and then assume that $P(n)$ holds for some even $n$ and show that $$P(n) \implies P(n+2)?$$

Whilst I'm almost positive that what I've written above is correct, I'd like some confirmation of that. I tried it out on the first example I could think of, that every even number is divisible by $2$.

Whilst this follows from the definition of an even number almost directly, I thought I'd give it a go with my new found induction process. Since $n=0$ is even and obviously divisible by $2$ and assuming that some even $n$ is divisible by $2$, then we can write $n = 2k$ for some natural $k$ so that $n+2 = 2(k+1)$, which is divisible by $2$ and hence every even number is divisible by $2$. This seems very fishy to me, almost circular. But that's not really the point I'm trying to make.

What I'm looking for: Is what I said about $P(n) \implies P(n+2)$ correct? Secondly, what examples are there of results that only hold for even numbers that this method of induction would work on? I racked my head and the best I could come up with was the even numbers are divisible by $2$ and $(-1)^n = 1$ for even $n$. Both are very trivial and uninteresting to prove. Do you have any interesting examples of theorems/results that work only for even numbers that is provable using this method of induction?

Edit: The main focus of this question is to try and gather a few interesting (read non-trivial) examples of results that hold true for only even numbers and for which induction is an available proof-method.

• It is possible to perform induction on larger-than-countable sets. See en.wikipedia.org/wiki/Transfinite_induction – Erick Wong Jul 11 '15 at 21:25
• @ErickWong, I just went through those links and holy cow, that is amazing! You can induct on any well-ordering then? – Zain Patel Jul 12 '15 at 1:27
• Yes, you can. The inductive step has a slightly different feel to it than $P(n) \implies P(n+1)$. In a transfinite induction, not every element can be reached by just adding $+1$ finitely many times. So the induction generally involves proving that $P(n)$ is true assuming $P(m)$ is true for all $m < n$. For instance there will be an ordinal $\omega$ which is greater than all positive integers, and you need to prove $P(\omega)$ follows from "$P(n)$ for all $n \in \mathbb N$" ($\omega$ itself, being infinite, doesn't belong to $\mathbb N$). – Erick Wong Jul 12 '15 at 3:35

Yes, you can use induction to prove a property holds for a subset of integers by ordering your subset some way with a least element, and then proving that if the property holds for all earlier elements in the subset (or just the previous one, if you like), then it holds for the next element in your subset. This basically is just using a bijection $f$ from positive integers to elements in your subset, such that you can prove that if a property is true for $f(n)$ then it is true for $f(n+1)$ (and of course, that it's true for $f(1)$). So if your subset is the positive even integers, you would use the bijection $f(n) = 2n$ and then standard induction applies.

• Okay, so I've understood that to prove that $P$ is true for a countable set, then it suffices to prove that $P(f(n))$ is true for all $n$ where $f(n)$ is the bijection from the naturals to the countable set. Thanks for that. +1. – Zain Patel Jul 11 '15 at 18:12

What I'm noticing from listing all those sets down is that induction seems to work for proving results are true for countably infinite sets? Is that an accurate observation.

That is correct.

To prove a proposition $P$ is true for all positive even numbers, would I need to assume a base case of $n=0, 2, \text{etc}\ldots$ and then assume that $P(n)$ holds for some even $n$ and show that $$P(n) \implies P(n+2)?$$

Yes, that will work.

Since n=0 is even and obviously divisible by 2 and assuming that some even n is divisible by 2, then we can write n=2k for some natural k so that n+2=2(k+1), which is divisible by 2 and hence every even number is divisible by 2. This seems very fishy to me, almost circular. But that's not really the point I'm trying to make.

This overall is fine.

Another way to prove that $P(n)$ holds for all (non-negative) even $n$ is to prove that $P(2n)$ holds for all $n$. (It sounds like this is what you are saying.) So if you want to prove that $(-1)^n = 1$ for all even numbers (call this $P(n)$, you could first observe that $P(0)$ is true. Then you can prove that if $P(2n)$ is true, then $P(2(n+1))$ is true. So if $(-1)^{2n}$ is even, then $(-1)^{2(n+1)} = (-1)^{2n + 2} = (-1)^{2n}(-1)^2 = \dots$

• +1 Astute. I hadn't thought about the $P(2n)$ thing. So basically, to prove that $P$ holds for any countably infinite sets, it suffices to prove that $P(f(n))$ holds for all $n$ where $f(n)$ is the bijection from the naturals to your countably infinite set? – Zain Patel Jul 11 '15 at 18:06
• @ZainPatel: That's right. – Thomas Jul 11 '15 at 18:07

You may perform induction on any well-ordered set. Fortunately, the naturals, and every subset thereof, are well-ordered. The integers and rationals are not well-ordered in the usual way, but it is possible to use a nonstandard ordering to make them well-ordered.

• I was under the expression that a well-ordering of the reals existed under the ZFC axioms? – Zain Patel Jul 11 '15 at 18:02
• @ZainPatel Yes, and such an ordering is also non-standard. The main difference is that integers and rationals can be given well-orderings that are fairly tractable and useful (e.g. integers can be ordered by absolute value, and rationals by height), while any well-ordering of the reals will be somewhat abstract. At some point you still need to carry out an induction argument on the ordering structure, no matter what structure you impose. – Erick Wong Jul 11 '15 at 21:24