# Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and $m+1$? (If that's needed)

Give a direct proof that if $n$ and $m$ are even integers, then $n + m$ is an even integer is true.

• An induction proof would be extreme overkill. Try a direct proof using the definition of an even integer. – Adriano Oct 20 '14 at 19:25

## Easy Proof

Let $n=2j$ and $m=2k$ where $k, j \in \mathbb{Z}$. Then $n+m=2j+2k=2(j+k)$ which is even because $j+k$ is an integer.

## Inductive proof

Regular induction requires a base case and an inductive step. When we increase to two variables, we still require a base case but now need two inductive steps. We'll prove the statement for positive integers $\mathbb{N}$. Extending it to negative integers can be done directly.

### Base case

Let the base case be the case where $n=2$ and $m=2$. Clearly, $n+m=4$ is even.

### Inductive step for $n$

Suppose that $n+m$ is even for some $n, m$. We will show that $(n+2) + m$ is even. Since $n+m$ is even it can be expressed as $2k$, so we rewrite $(n+2)+m$ to $2k+2=2(k+1)$ which is even.

### Inductive step for $m$

Suppose that $n+m$ is even for some $n, m$. We will show that $n + (m+2)$ is even. Since $n+m$ is even it can be expressed as $2k$, so we rewrite $n+(m+2)$ to $2k+2=2(k+1)$ which is even.

This completes the proof. To intuitively understand why the induction is complete, consider a concrete example. We will show that $8+6$ is even using a finite inductive argument.

First note that the base case shows $2+2$ is even. Then by the inductive step for $n$, $4+2$ is even. Then by the inductive step for $n$, $6+2$ is even. Then by the inductive step for $n$, $8+2$ is even.

Then by the inductive step for $m$, $8+4$ is even. Then by the inductive step for $m$, $8+6$ is even, which completes the proof.