Induction Proofs

• Sep 6th 2012, 02:47 PM
Patriotx12
Induction Proofs
Prove by induction:

1. If g and h are commuting elements of G, prove g commutes with every positive integer power of h: ghn= hng for all positive integers n.Then prove gmhn = hngm for all positive integers m and n. Is this true when m and n are arbitrary integers?

2. If g and h are commuting elements of G, prove (gh)n = gnhn for all positive integers n.

Here's my attempt at solving 1, I'm just not sure if it's correct, or if more needs to be proved.

ghn = hng

Base step: let n = 1
gh = hg

Assume ghk = hkg

ghk+1= hk+1g
ghkh = hkhg
ghk = hkg

Is that done correctly, and if so would it end the proof? And can the others be proved in the same way?
• Sep 6th 2012, 04:47 PM
johnsomeone
Re: Induction Proofs
The first line after your "Assume g(h^k)=(h^k)g" was unjustified. You hadn't yet given a reason for asserting that g(h^(k+1))=(h^(k+1))g. In fact, proving that statement is the goal of the induction.
Prop1: Let g,h in group G such that gh = hg. Then for all integers n>=1, g(h^n)=(h^n)g.
Proof: By induction. Define Statement(n) = "g(h^n)=(h^n)g"
Statement(1) is true, since gh=hg is given.
Assume Statement(k) is true for some k>=1. Then g(h^k)=(h^k)g. Multiply on right byh: (g(h^k))h=((h^k)g)h.
Now associative property of group operation gives: g((h^k)h)=(h^k)(gh). But (h^k)h=h^(k+1) by def of exponent, and gh = hg is given.
Thus g(h^(k+1))=(h^k)(hg). Apply associative again to the RHS, getting g(h^(k+1))=((h^k)h)g and then again note that (h^k)h=h^(k+1).
Thus g(h^(k+1))=(h^(k+1))g. Thus Statement(k+1) is true (since that's exactly what Statement(k+1) asserts).
Thus have proven that Statement(1) is true, and also: if Statement(k) is true for any k>=1, then Statement(k+1) must also be true.
The line above means that we've proven by induction that Statement(n) is true for all n>=1.
Thus g(h^n)=(h^n)g for all n>=1. QED
• Sep 6th 2012, 05:03 PM
HallsofIvy
Re: Induction Proofs
Quote:

Originally Posted by Patriotx12
Prove by induction:

1. If g and h are commuting elements of G, prove g commutes with every positive integer power of h: ghn= hng for all positive integers n.Then prove gmhn = hngm for all positive integers m and n. Is this true when m and n are arbitrary integers?

2. If g and h are commuting elements of G, prove (gh)n = gnhn for all positive integers n.

Here's my attempt at solving 1, I'm just not sure if it's correct, or if more needs to be proved.

ghn = hng

Base step: let n = 1
gh = hg

True but it would be better to state "it is given that g and h commute".

Quote:

Assume ghk = hkg

ghk+1= hk+1g
ghkh = hkhg
How do you go from this line to the next? That is, how do you justify cancelling those "h"s?

Quote:

ghk = hkg

Is that done correctly, and if so would it end the proof? And can the others be proved in the same way?
Also, you have gone from what you want to get to what you are assuming in the "induction hypothesis"- that's okay (and is called "synthetic proof") as long as every step is reversible but I think a direct proof is always preferable.
From ghk= hkg, the induction hypothesis, multiply both sides of the equation, on the [b]right[b], by h:
gh[sup]k[sup]h= hkgh. The left side is clearly ghk+1 but how do you get hkgh to hk+1g? (Remember that our basic hypothesis is that g and h commute.)

Now try the same thing with the next problem.