3
$\begingroup$

Claim:

any two positive integers are equal

Proof:

Let $A(n)$ be statement:

if $a$ and $b$ are any two positive integers such that $\max(a,b)=n$ then $a=b$

Suppose $A(r)$ is true. Let $a$ and $b$ be any two positive integers such that $\max(a,b)=r+1$. Consider the two integers $p=a-1$ and $q=b-1$: then $\max(p,q)=r$. Hence $p=q$, for we are assuming $A(r)$ to be true. It follows that $a=b$; hence $A(r+1)$ is true. $A(1)$ is obviously true, for $max(a,b)=1$ implies $a=b=1$. Therefore by mathematical induction, $A(n)$ is true for every $n$.

Now if $a$ and $b$ are any two positive integers whatsoever, denote $\max(a,b)$ by $r$. Since $A(n)$ has been shown to be true for every $n$, in particular $A(r)$ is true. Hence $a=b$.

1 Answers 1

10

Presumably your induction assumption is that the result is true for any positive integers whose maximum is $r$. You are then trying to prove the result for maximum equal to $r+1$. Note that $a-1$ or $b-1$ need not be positive, so the induction assumption is not sufficient.