5
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.