A question about induction. Are we allowed to perform induction only on set of natural numbers or can we also perform induction on say set of even integers?
 A: In the strictest theoretic sense, no. Mathematical induction applies only to predicates taking an argument $n \in \Bbb{N}$ (i.e. a true/false statement that depends on an unknown $n \in \Bbb{N}$, e.g. "$n$ is even"). It states that, if we have a predicate $P(n)$, where $n \in \Bbb{N}$, such that $P(0)$ is true and $P(n) \implies P(n + 1)$ for all $n \in \Bbb{N}$, then $P(n)$ is true for all $n \in \Bbb{N}$.
In practice, this principle is far more flexible. If we want to prove $Q(n)$ for all $n \ge 7$, we can simply let $P(n)$ be $Q(n + 7)$ and apply induction as above. If we want to prove $Q(n)$ for positive even integers, that's easy too: let $P(n)$ be $Q(2n + 2)$, then use induction.
We could even induct over all the integers. If we wish to prove $Q(n)$ for all $n \in \Bbb{Z}$, we let $P(n)$ be $Q(n)$ and $P'(n)$ be $Q(-n)$ for $n \in \Bbb{N}$. We can then prove $P(n)$ and $P'(n)$ for all $n$ using induction, and that will prove $Q(n)$ for all $n \in \Bbb{Z}$. Induction over all even integers would work similarly.
What sets can't you use induction on? Essentially, our predicates need to be indexed by a well-ordered set, and preferably order-isomorphic to $\Bbb{N}$ (unless you use the more complex transfinite induction). Inducting over the real numbers wouldn't work so well, because there is no "next" real number, so the induction step is kinda meaningless.
I hope that helps.
