A general logic/Induction question

[daon]

This is not an assignmet, I just have a question on using induction.I don;t think I've ever attempted using it when proving an implication, only when trying to prove equality/inequality.

Lets say I'm trying to prove that for non-negative integers a,b, $\displaystyle a^m=b^m \Rightarrow a=b$.

In my inductive step, I am assuming both that $\displaystyle a^{m+1}=b^{m+1}$ and $\displaystyle a^m = b^m \Rightarrow a=b$ for all non-negtaive integers up to m, right? So, would this be alright:

$\displaystyle (a^m=b^m \,\,\Longrightarrow\,\, a=b) \,\,\Longleftrightarrow\,\, (a^ma=b^ma \,\,\Longrightarrow\,\, a=b)$
$\displaystyle \,\Longleftrightarrow\,\, (a^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b)$
\(\displaystyle \,\Longleftrightarrow\,\,
(b^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b)\) Since we are assuming a^(m+1)=b^(m+1)

And thus by LHS cancellation:

$\displaystyle (b^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b) \,\Longleftrightarrow\,\, (b = a \Longrightarrow a=b)$ Which, we know is true, thus P(n) is true.

I know I should probably reverse the steps to make it clear what I proved, but besides that, is there anything wrong with what I just did?

 

[JakeD]

This is not an assignmet, I just have a question on using induction.I don;t think I've ever attempted using it when proving an implication, only when trying to prove equality/inequality.

Lets say I'm trying to prove that for non-negative integers a,b, $\displaystyle a^m=b^m \Rightarrow a=b$.

In my inductive step, I am assuming both that $\displaystyle a^{m+1}=b^{m+1}$ and $\displaystyle a^m = b^m \Rightarrow a=b$ for all non-negtaive integers up to m, right? So, would this be alright:

$\displaystyle (a^m=b^m \,\,\Longrightarrow\,\, a=b) \,\,\Longleftrightarrow\,\, (a^ma=b^ma \,\,\Longrightarrow\,\, a=b)$
$\displaystyle \,\Longleftrightarrow\,\, (a^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b)$
\(\displaystyle \,\Longleftrightarrow\,\,
(b^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b)\) Since we are assuming a^(m+1)=b^(m+1)

And thus by LHS cancellation:

$\displaystyle (b^{m+1}=b^ma \,\,\Longrightarrow\,\, a=b) \,\Longleftrightarrow\,\, (b = a \Longrightarrow a=b)$ Which, we know is true, thus P(n) is true.

I know I should probably reverse the steps to make it clear what I proved, but besides that, is there anything wrong with what I just did?

Stripping down the logic, you're assuming $\displaystyle a^{m+1}=b^{m+1}$, know that for all $\displaystyle n \le m$, $\displaystyle a^{n}=b^{n} \ \Longrightarrow\ a=b$ and must show that $\displaystyle a=b$ results. To use the known implication to get the result, you must show $\displaystyle a^{m+1}=b^{m+1}\ \Longrightarrow\ \exists n \le m, \ a^{n}=b^{n}.$ But you haven't shown that (and I don't see how to do it.)