Thread: Inverse proof

I'm asked to prove (a1 a2 a3 ... an) ^-1 = (an^-1 ... a1^-1)

Here's my induction proof. Please critique and let me know what needs changed or improved.

Base: n=1: (a1)^-1 = a1^-1 by def of inverse

We will assume that (a1 a2 a3 ... a(n-1)) ^-1 = (a(n-1)^-1 ... a1^-1) and use it to show our original statement.

Now, (a1 a2 a3 ... an) ^-1 = [(a1 a2 a3 ... a(n-1)) (an)] ^-1

= (an)^-1 (a1 a2 a3 ... a(n-1)) ^-1 by def of inverse

= (an)^-1 (a(n-1)^-1 ... a1^-1) by ind. hyp.

= (an^-1 ... a1^-1) as desired. QED

What do you think?

Hey jzellt.

One typical way of this proof is to do the following:

Let x = (a1a2a3...an)^(-1) then

x*x^-1 = e (identity) which implies

(a1a2a3...an)^(-1)*(a1a2a3...an) = e.

Now basically you just post-multiply in the reverse order so as an example if we post-multiply both by (an)^-1 we get

(a1a2a3...an)^(-1)*(a1a2a3...an-1)(an)(an^-1) = e*an^(-1) or
(a1a2a3...an)^(-1)*(a1a2a3...an-1) = an^(-1)

If you do this to remove all the non-inverted terms you get the identity.

Thanks. But, I guess I failed to mention that I have to use induction

Well instead of using a1,...,an just let a1 represent a1 up to ak and a2 to be ak+1.

Originally Posted by jzellt

Base: n=1: (a1)^-1 = a1^-1 by def of inverse

We will assume that (a1 a2 a3 ... a(n-1)) ^-1 = (a(n-1)^-1 ... a1^-1) and use it to show our original statement.

Now, (a1 a2 a3 ... an) ^-1 = [(a1 a2 a3 ... a(n-1)) (an)] ^-1

= (an)^-1 (a1 a2 a3 ... a(n-1)) ^-1 by def of inverse

= (an)^-1 (a(n-1)^-1 ... a1^-1) by ind. hyp.

= (an^-1 ... a1^-1) as desired. QED

First, you should say what a_i's are: real numbers, matrices, elements of a nonabelian group, etc. Also, it may be better to view [(a1 a2 a3 ... a(n-1)) (an)]^-1 = (an)^-1 (a1 a2 a3 ... a(n-1))^-1 as an instance of the theorem for n = 2. Then the induction step for n will use two induction hypotheses: for n - 1 and for 2. Correspondingly, you have to prove the base case for n = 2 in addition to the one for n = 1. Finally, the base case for n = 1 holds by reflexivity of equality. The definition of inverse is not used there, but it is used for n = 2.

Originally Posted by jzellt

I'm asked to prove (a1 a2 a3 ... an) ^-1 = (an^-1 ... a1^-1)
...
Base: n=1: (a1)^-1 = a1^-1 by def of inverse
...
Now, (a1 a2 a3 ... an) ^-1 = [(a1 a2 a3 ... a(n-1)) (an)] ^-1
= (an)^-1 (a1 a2 a3 ... a(n-1)) ^-1 by def of inverse
...

Two related comments (I made a mistake in my second comment - you should ignore it):
First and foremost, the statement following your "Now" is true, but it isn't true "by def of inverse". The reason that statement is true is actually the heart of the induction. It's true because:

$\displaystyle (ab)^{-1} = b^{-1}a^{-1}$.

And what is that? It's your inductive claim for n=2!! Now it is true, but you need to show that it's true. It isn't true "by def of inverse".

**** THIS IS MY MISTAKE. IGNORE IT. [See emakarov's comment under this one] ****
The "CLASSIC PROOF BY INDUCTION" beneath this is still (in)valid though
************************************************** *******************
Second point, and this one is more subtle, so sorry if it confuses you. Your inductive step doesn't apply in moving from the n=1 case to the n=2 case. Plug n=1 into your inductive assumptions. What does (a1 a2 a3 ... a(n-1)) look like? It doesn't make sense when n=1, does it? It makes sense when n=2 (then (a1 a2 a3 ... a(n-1)) = (a1)). So even ignoring my first point above, what you've proved, with S(n) being your inductive hypothesis for n, is that:
1) S(1) is true.
2) For all n >= 2, if S(n) is true, then S(n+1) is true.
Do you see how that's broken? Do you see how S(1) doesn't get you to S(2)? How those two statements don't guarantee that, say, S(304) is true?

Now, notice how the truth of P(2) is the issue in my first point, and is again kinda the issue in this, my second point? That's because P(2) is the HEART of the problem. P(2) is why the induction holds.

This comes up fairly often, and is a subtle point that's often more confusing than enlighting. However, it's possible that neglecting this could to cause you to prove false statements by induction! I've included a classic example below.

------------------------------------------------------------------------------------------------------------
The upshot of my two points is that, while showing that it's true for n=1 is great, you need to also show that it's true for n=2. It needs to be proven, not-inductively, but directly, for both n=1 and n=2.

------------------------------------------------------------------------------------------------------------
CLASSIC PROOF BY INDUCTION: *** All billiard balls have the same color! ***
Proof:

Let S(n) = "Every group of n billiard balls has the same color."

S(1) = "Every group of 1 billiard balls has the same color." That's obviously true, since there's only one, and it has the same color as itself.

Assume S(n) is true. Then "Every group of n billiard balls has the same color." I'll now show that, on this that assumption S(n) that is true, it follows that S(n+1) is true.

Take any n+1 billiard balls. For convenience, label them B1, B2, ... B(n+1).

Hold B(n+1) out and consider the set {B1, B2, ... B(n)}. That's a set of n billiard balls, so by induction (the assumtion S(n)), they all have the same color.

Now hold B1 out and consider the set {B2, B3, ... B(n+1)}. That's again a set of n billiard balls, so by induction (the assumption S(n)), they all have the same color.

So B(n+1) has the same color as B2. But we know that {B1, B2, ... B(n)} all have the same color, which is B2's color, and so which is B(n+1)'s color.

Thus {B1, B2, ... B(n+1)} all have the same color.

Since this was any collection of n+1 billiard balls, this proces S(n+1).

In summary, I've proven:
1) S(1) is true.
2) If S(n) is true, then S(n+1) is true.
Therefore, by induction, I know S(n) is true for all n.
Therefore, all the billiard balls in the universe have the same color.
(And here I thought I remembered some having different colors...)

OK - what's the problem? How and why did the induction fail? (or did it, buahahaha...)

Originally Posted by johnsomeone

First and foremost, the statement following your "Now" is true, but it isn't true "by def of inverse". The reason that statement is true is actually the heart of the induction. It's true because:

$\displaystyle (ab)^{-1} = b^{-1}a^{-1}$.

And what is that? It's your inductive claim for n=2!! Now it is true, but you need to show that it's true. It isn't true "by def of inverse".

The OP can prove this as a lemma before the inductive proof. This is why I said in post #5 that it may be better to view [(a1 a2 a3 ... a(n-1)) (an)]^-1 = (an)^-1 (a1 a2 a3 ... a(n-1))^-1 as an instance of the theorem for n = 2; however, this is not required. Further, we prove $\displaystyle (ab)^{-1} = b^{-1}a^{-1}$ by showing that $\displaystyle (b^{-1}a^{-1})(ab)=1$. This is very easy and requires applying the properties or axioms of associativity, inverse and unit. Thus, it could be said that this fact follows from the definition of inverse, though the simplicity of the overall theorem probably requires a more detailed explanation.

Originally Posted by johnsomeone

Second point, and this one is more subtle, so sorry if it confuses you. Your inductive step doesn't apply in moving from the n=1 case to the n=2 case. Plug n=1 into your inductive assumptions. What does (a1 a2 a3 ... a(n-1)) look like? It doesn't make sense when n=1, does it? It makes sense when n=2 (then (a1 a2 a3 ... a(n-1)) = (a1)). So even ignoring my first point above, what you've proved, with S(n) being your inductive hypothesis for n, is that:
1) S(1) is true.
2) For all n >= 2, if S(n) is true, then S(n+1) is true.

No, the OP showed S(1) and for all n >= 2, S(n-1) implies S(n).

Right you are on both counts. Thanks for catching my error in the second comment.

my proof would be as follows:


$\displaystyle (a_1a_2\dots a_{n-1}a_n)(a_n^{-1}a_{n-1}^{-1}\dots a_2^{-1}a_1^{-1}) =$

$\displaystyle (a_1a_2\dots a_{n-1})(a_na_n^{-1})(a_{n-1}^{-1}\dots a_2^{-1}a_1^{-1}) =$ (by associativity *used "several" times: see below)

$\displaystyle (a_1a_2\dots a_{n-1})(e)(a_{n-1}^{-1}\dots a_2^{-1}a_1^{-1}) =$

$\displaystyle (a_1a_2\dots a_{n-1})(a_{n-1}^{-1}\dots a_2^{-1}a_1^{-1}) = e$ (by the induction hypothesis)

note there is a big HOLE in the proof: the step involving associativity:

$\displaystyle (a_1a_2\dots a_{n-1}a_n) = (a_1a_2\dots a_{n-1})(a_n)$

the reason being, we can put parentheses in an n-fold product a LOT of different ways. one hopes you have proved the somewhat more difficult theorem that any "grouping" of multiplicative terms yields the same n-fold product in G earlier, because it is KEY.