Mastering my "prove by induction" skills.

Question

Let $a, b \in G$ where $G$ represents a group. Prove that $ab^na^{-1} = (aba^{-1})^n, n \in \mathbb{N} \setminus \{0\}$.

My goal is to master "prove by induction skill", so I'll try to be as explicit and consistent, as possible. Please, acknowledge the fact that my prove is technically correct.

So, first of all, there is at least one $n_0 = 1 \in \mathbb{N} \setminus \{0\}$, for which the statement above holds true.

Now I have to show that statement will remain true for the $n_0 + 1$: $$ab^2a^{-1} = (aba^{-1})^1(aba^{-1})^1 = ab\underbrace{a^{-1}a}_\textrm{e}ba^{-1} = abba^{-1} = ab^2a^{-1}$$

The last thing to do is to show that $n + 1$ step won't become false regardless of what $n \geq n_0$ chosen: $$ab^{n + 1}a^{-1} = (ab^na^{-1})(aba^{-1}) = ab^n(a^{-1}a)ba^{-1} = ab^{n+1}a^{-1}$$

As such, the statement above must be true for each element in the specified set.

Answer 1

As mentioned in the comments above, you have a bit of an organizational issue. The goal is to show that $ab^{n}a^{-1}=(aba^{-1})^{n}$. It does us no good to show that $ab^na^{-1}=ab^na^{-1}$, we knew that to be true already.

For your induction step it should read something more like:

$\begin{array}{rlr}(aba^{-1})^{n+1}&=(aba^{-1})^n(aba^{-1})&\text{by properties of exponents}\\&=(ab^na^{-1})(aba^{-1})&\text{by induction hypothesis}\\&=ab^n(a^{-1}a)ba^{-1}&\text{by associativity}\\&=ab^nba^{-1}&\text{by properties of inverses}\\&=ab^{n+1}a^{-1}&\text{by properties of exponents}\end{array}$

Note that where we begin was one side of the desired equality and where we end is the other side of the desired equality. You could also have written this in the opposite order, having started with $ab^{n+1}a^{-1}$ and ended with $(aba^{-1})^{n+1}$ by having essentially reversed the steps outlined above.

It should also be clearly labeled where you used your induction hypothesis, perhaps to the side like this or if you are short on space and do it all in one line like this instead $\dots = (aba^{-1})^n(aba^{-1})\begin{smallmatrix}=\\I.H.\end{smallmatrix}(ab^na^{-1})(aba^{-1})=\dots$. Its not absolutely necessary that you explain every step like I have above, especially if your intended audience doesn't need such an explanation, but where the induction hypothesis is used should still be labeled.

Answer 2

• Let $P(n)$ be the statement that $ab^na^{-1}=(aba^{-1})^n.$

• State what you want to show: $$\forall n \geq 1, ab^na^{-1}=(aba^{-1})^n.$$

that is $\forall n \ge 1, P(n)$ is true.

• Next, check base case, verify if it is true for $n=1$. LHS would be $ab^1a^{-1}$ while RHS would be $(aba^{-1})^1=aba^{-1}$. Hence $P(1)$ is true.

• State that induction hypothesis: Assume $P(k)$ is true. That is we have $ab^ka^{-1}=(aba^{-1})^k$.

• We want to show that $P(k+1)$ is true. That is we intend to show that $ab^{k+1}a^{-1} = (aba^{-1})^{k+1}.$

Proof for the induction step:

\begin{align}ab^{k+1}a^{-1}&=a(b^kb)a^{-1}\\&=ab^keba^{-1}\\&=ab^k(a^{-1}a)ba^{-1} \\ &=(ab^ka^{-1})(aba^{-1}) \\ &=(aba^{-1})^k(aba^{-1}), \text{, by induction hypothesis} \\ &=(aba^{-1})^{k+1}\end{align}

Since $P(n)$ is true for $n=1$ and we have proven that $P(k) \implies P(k+1)$, $P(n)$ is true for all natural number.

Be very clear where do you apply the induction hypothesis.

Answer 3

No.

The steps of proof by induction go:

Base Step: Show that there is $n_0$ where this is true.

If $n_0 = 1$, you need to show that $ab^1a^{-1} = (aba^{-1})^{1}$.

You did not show that.

(As $g^1 = g$ by definition: $ab^{1}a^{-1} = aba^{-1} = (aba^{-1})^1$.)

You do NOT have to show that it remains true for $n_0 + 1$. You can but that is will be redundant when you do the induction step.

Inductions Step: Prove that if the statement is true for $n$ then it will be true for $n+1$.

It's not enough to prove that it doesn't "become false". You must prove it is true $n+1$ assuming it true for $n$.

You state $ab^{n + 1}a^{-1} = (ab^na^{-1})(aba^{-1}) = ab^n(a^{-1}a)ba^{-1} = ab^{n+1}a^{-1}$

which means ... $ab^{n+1}a^{-1} = ab^{n+1} a^{-1}$??? What you started with is equal to itself. That ... gets us nowhere.

And it doesn't matter if that is true.

We need to prove that $ab^{n+1}a^{-1} = (aba^{-1})^{n+1}$. And we are allowed to assume that $ab^na^{-1} = (aba^{-1})^n$ in order to prove that.

So to prove it:

$ab^{n+1}a^{-1} = ab^n*ba^{-1} = ab^n*e*ba^{-1} = ab^n*(a^{-1}a)*ba^{-1}$.

$= (ab^na^{-1})aba^{-1}$.

NOW we were allowed to assume that $ab^na^{-1} = (aba^{-1})^{n}$ for that particular $n$. We don't (at this point) know which values it is true for. We did know it is true for $n=n_0$ in the base step, but we don't use that here. We are simply trying to show that if it is true for some value $n$, then it will follow that it is true for $n+1$.

So we are assuming it is true for $n$. But we don't know if it is true for any other values.

So $(ab^na^{-1}) = (aba^{-1})^n$ can be assumed.

So $ab^{n+1}a^{-1} = (ab^na^{-1})aba^{-1}$

$= (aba^{-1})^n(aba^{-1})$

$= (aba^{-1})^{n+1}$.

That is the result we had to prove. .... IF we assume the result was true for that particular $n$.

.....

Now, that is enough to say we are done. The unspoken implication of the proof is this:

We have proven:

1) $(ab^1a^{-1}) = (aba^{-1})^1$

2) IF $ab^na^{-1}=(aba^{-1})^n$ THEN $ab^{n+1}a^{-1} = (aba^{-1})^{n+1}$.

We can apply 2) to 1) and conclude:

3a) $ab^2a^{-1} = (aba^{-1})^2$

(we did NOT have to prove it directly)

And we can apply 2) to 3a) and conclude:

3b) $ab^3a^{-1} = (aba^{-1})^3$

And we can apply 2) to 3b) ad conclude:

3c) $ab^4a^{-1} = (aba^{-1})^4$

And so on....

We don't need to state these "and so on" statements every single time we do a proof by induction. We assume that if we are given:

1) $P(1)$ is true.

2) IF $P(n)$ is true for some $n$ then it will be true for $P(n+1)$

we can conclude

3) $P(n)$ is true for all $n \in \mathbb N$.

We accept this as a basic logical truism.

P.S.

I think you made some weird typos.

You typed $ab^2a^{-1} = (aba^{-1})^1(aba^{-1})$ which .... we have no explanation for. And we conclude $ab^2a^{-1}=.... =ab^2a{-1}$. Which is ... where we started. And you never say anything about $(aba_{-1})^2$ which was the entire point.

You do the exact same thing later.

You typed $ab^{n+1}a^{-1} = (ab^na^{-1})^1(aba^{-1})$ which .... we have no explanation for. And we conclude $ab^{n+1}a^{-1}=.... =ab^{n+1}a{-1}$. Which is ... where we started. And you never say anything about $(aba_{-1})^n$ which was the entire point.

I think you meant to type:

$(aba^{-1})^2 = (aba^{-1})(aba^{-1}) = abeba^{-1} = ab^2a^{-1}$

And

$(aba^{-1})^{n+1} =(aba^{-1})^n(aba^{-1}) = (ab^na^{-1})(aba^{-1}) ab^n(a^{-1}a)ba^{-1} = ab^{n+1}a^{-1}$.