Help with algebra for a proof: manipulating an expression

Sep 2009
71
0
I have a proof that I have to do.

for all positive natural numbers n and for any integers a and b such that a != b a^n - b^n is divisible by a-b

the induction hypothesis is to assume the a^k - b^k is divisible by a-b

I need to show that a^(k+1) - b^(k+1) is divisible by (a-b). I have seen the solution floating around on the internet. The expression can be manipulated into the form
a(a^k - b^k) + b^k(a -b) which is divisible by (a-b) both directly in the second term and by the induction hypothesis in the first. I don't necessarily want to know how to get to this result. But how do I THINK about how to get to the result?

Any advice would be helpful. Thanks
 
Jul 2010
12,211
522
St. Augustine, FL., U.S.A.'s oldest city
Re: Help with algebra for a proof: manipulating an expressio

Obviously, the base case \(\displaystyle P_1\) is true, so the induction hypothesis \(\displaystyle P_n\) is:

\(\displaystyle a^n-b^n=k(a-b)\)

Now, my inclination is to multiply both sides by \(\displaystyle (a+b)\):

\(\displaystyle \(a^n-b^n\)(a+b)=k(a-b)(a+b)\)

Now arrange as follows:

\(\displaystyle a^{n+1}-b^{n+1}=k(a-b)(a+b)-ab\(a^{n-1}-b^{n-1}\)\)

And the rest follows from applying the induction hypothesis to the second term on the right.
 
Sep 2009
71
0
Re: Help with algebra for a proof: manipulating an expressio

MarkFL said:
Obviously, the base case \(\displaystyle P_1\) is true, so the induction hypothesis \(\displaystyle P_n\) is:

\(\displaystyle a^n-b^n=k(a-b)\)

Now, my inclination is to multiply both sides by \(\displaystyle (a+b)\):

\(\displaystyle \(a^n-b^n\)(a+b)=k(a-b)(a+b)\)

Now arrange as follows:

\(\displaystyle a^{n+1}-b^{n+1}=k(a-b)(a+b)-ab\(a^{n-1}-b^{n-1}\)\)

And the rest follows from applying the induction hypothesis to the second term on the right.
So does this mean I should be using strong induction then? since \(\displaystyle a^{n-1} - b^{n-1}\) is less than \(\displaystyle a^{n} - b^{n}\)?