Proof by Mathematical Induction-(x^n - a^n) is divisible by (x-a) for all values of n

[ptaxler]

Hello All, I am just starting with Maths and made an attempt to prove this formula using "Proof by Mathematical Induction" : (x^n - a^n) is divisible by (x-a) for all positive values of n.

Ask from this Thread : I need someone to verify this solution and point out any mistakes.

Below is my attempt to solve this:

1. For n=1 ,

==> (x^1 - a^1) is divisible by (x-a) 
==> (x-a)/(x-a) = 1

2. Let's assume this is true for n = k,

==> (x^k - a^k) is divisible by (x-a)
==> (x^k - a^k)/(x-a) = m ; where m is an integer since  (x^k - a^k) is divisible by (x-a)

3. Now, we have to prove this for n = k+1

==> [x^(k+1) - a^(k+1)] is divisible by (x-a)
==> [x^(k+1) - a^(k+1)]/(x-a) = l                ; where l is an integer
==> [x(x^k) -a(a^k)]/(x-a) = l
==> [x(x^k) -x(a^k) + x(a^k) -a(a^k)]/(x-a) = l  ; (adding and subtracting x(a^k)
==> [x(x^k - a^k) + a^k(x-a)]/(x-a) = l
==> x(x^k - a^k)/(x-a) + a^k(x-a)/(x-a) = l
==> x(m) + a^k = l                               ; [(substituting (x^k - a^k)/(x-a) = m from Step 2]

[x^(k+1) - a^(k+1)] is divisible by (x-a)since there is no remainder in Step 3.

Hence Proved that (x^n - a^n) is divisible by (x-a) for all positive values of n.

 

[stapel]

"Proof by Mathematical Induction": (xⁿ - aⁿ) is divisible by (x-a) for all positive values of n.

I need someone to verify this solution and point out any mistakes.

Below is my attempt to solve this:

\(\displaystyle \mbox{1. For }\, n\, =\, 1,\, x^1\, -\, a^1\, \mbox{ is divisible by }\, x - a\)

\(\displaystyle \Rightarrow\, \dfrac{x\, -\, a}{x\, -\, a} = 1\)

You have the logic backwards. You've assumed divisibility, and proved that the result of the division is 1. What you need to do is start with the value of n, and then prove divisibility:

. . .\(\displaystyle \mbox{Let }\, n\, =\, 1.\, \mbox{ Then we have:}\)

. . . . .\(\displaystyle x^n\, -\, a^n\, =\, x^1\, -\, a^1\, =\, x\, -\, a\)

. . . . .\(\displaystyle \dfrac{x^n\, -\, a^n}{x\, -\, a}\, =\, \dfrac{x\, -\, a}{x\, -\, a}\, =\, 1\)

. . .\(\displaystyle \mbox{Then }\, x^n\, -\, a^n\, \mbox{ is divisible by }\, x\, -\, a\)

. . .\(\displaystyle \mbox{for }\, n\, =\, 1.\)

2. Let's assume this is true for n = k. Then:

\(\displaystyle \Rightarrow\, x^k\, -\, a^k\, \mbox{ is divisible by }\, x\, -\, a.\)

\(\displaystyle \Rightarrow\, \dfrac{x^k\, -\, a^k}{x\, -\, a}\, =\, m,\)

. . .\(\displaystyle \mbox{where }\, m\, \mbox{ is an integer}\)

. . .\(\displaystyle \mbox{since }\, x^k\, -\, a^k\, \mbox{ is divisible by }\, x\, -\, a\)

Correct, up to the last line. You aren't proving anything here; you're just clearly stating what you're assuming. You don't need to repeat the divisibility statement.

3. Now, we have to prove this for n = k+1

\(\displaystyle \Rightarrow\, x^{k+1}\, -\, a^{k+1}\, \mbox{ is divisible by }\, x\, -\, a\)

No. You're assuming what you actually need to prove. The fact of divisibility should come at the end of this step, having been proved (at the end) rather than assumed (at the beginning). So, using the standard steps for induction (here), we have:

. . .\(\displaystyle \mbox{Let }\, n\, =\, k\, +\, 1.\, \mbox{ Then:}\)

. . . . .\(\displaystyle x^{k+1}\, -\, a^{k+1}\, =\, x\, \cdot\, x^k\, -\, a\, \cdot\, a^k\)

. . . . . . .\(\displaystyle =\, x\, \cdot\, x^k\, -\, x\, a^k\, +\, x\, a^k\, -\, a\, \cdot\, a^k\)

. . . . . . .\(\displaystyle =\, x\, (x^k\, -\, a^k)\, +\, a^k\, (x\, -\, a)\)

. . .\(\displaystyle \mbox{This gives us:}\)

. . . . .\(\displaystyle \dfrac{x^{k+1}\, -\, a^{k+1}}{x\, -\, a}\, =\, \dfrac{x\, (x^k\, -\, a^k)\, +\, a^k\, (x\, -\, a)}{x\, -\, a}\)

. . . . . . .\(\displaystyle =\, \dfrac{x\, (x^k\, -\, a^k)}{x\, -\, a}\, +\, \dfrac{a^k\, (x\, -\, a)}{x\, -\, a}\)

. . .\(\displaystyle \mbox{Clearly, the second frac}\mbox{tion is divisible by }\, x\, -\, a.\)

. . .\(\displaystyle \mbox{For the first frac}\mbox{tion, by assumption, we get:}\)

. . . . .\(\displaystyle \dfrac{x\, (x^k\, -\, a^k)}{x\, -\, a}\, =\, x\, \left(\dfrac{x^k\, -\, a^k}{x\, -\, a}\right)\, =\, xm\)

. . .\(\displaystyle \mbox{Since each of the frac}\mbox{tions is divisible, so also is}\)

. . .\(\displaystyle \mbox{the original expres}\mbox{sion. So the relation is proved.}\)


Please reply if you're not understanding the difference, logically, between what you and I did. Thank you!

 

[ptaxler]

You have the logic backwards. You've assumed divisibility, and proved that the result of the division is 1. What you need to do is start with the value of n, and then prove divisibility:

. . .\(\displaystyle \mbox{Let }\, n\, =\, 1.\, \mbox{ Then we have:}\)

. . . . .\(\displaystyle x^n\, -\, a^n\, =\, x^1\, -\, a^1\, =\, x\, -\, a\)

. . . . .\(\displaystyle \dfrac{x^n\, -\, a^n}{x\, -\, a}\, =\, \dfrac{x\, -\, a}{x\, -\, a}\, =\, 1\)

. . .\(\displaystyle \mbox{Then }\, x^n\, -\, a^n\, \mbox{ is divisible by }\, x\, -\, a\)

. . .\(\displaystyle \mbox{for }\, n\, =\, 1.\)



Correct, up to the last line. You aren't proving anything here; you're just clearly stating what you're assuming. You don't need to repeat the divisibility statement.



No. You're assuming what you actually need to prove. The fact of divisibility should come at the end of this step, having been proved (at the end) rather than assumed (at the beginning). So, using the standard steps for induction (here), we have:

. . .\(\displaystyle \mbox{Let }\, n\, =\, k\, +\, 1.\, \mbox{ Then:}\)

. . . . .\(\displaystyle x^{k+1}\, -\, a^{k+1}\, =\, x\, \cdot\, x^k\, -\, a\, \cdot\, a^k\)

. . . . . . .\(\displaystyle =\, x\, \cdot\, x^k\, -\, x\, a^k\, +\, x\, a^k\, -\, a\, \cdot\, a^k\)

. . . . . . .\(\displaystyle =\, x\, (x^k\, -\, a^k)\, +\, a^k\, (x\, -\, a)\)

. . .\(\displaystyle \mbox{This gives us:}\)

. . . . .\(\displaystyle \dfrac{x^{k+1}\, -\, a^{k+1}}{x\, -\, a}\, =\, \dfrac{x\, (x^k\, -\, a^k)\, +\, a^k\, (x\, -\, a)}{x\, -\, a}\)

. . . . . . .\(\displaystyle =\, \dfrac{x\, (x^k\, -\, a^k)}{x\, -\, a}\, +\, \dfrac{a^k\, (x\, -\, a)}{x\, -\, a}\)

. . .\(\displaystyle \mbox{Clearly, the second frac}\mbox{tion is divisible by }\, x\, -\, a.\)

. . .\(\displaystyle \mbox{For the first frac}\mbox{tion, by assumption, we get:}\)

. . . . .\(\displaystyle \dfrac{x\, (x^k\, -\, a^k)}{x\, -\, a}\, =\, x\, \left(\dfrac{x^k\, -\, a^k}{x\, -\, a}\right)\, =\, xm\)

. . .\(\displaystyle \mbox{Since each of the frac}\mbox{tions is divisible, so also is}\)

. . .\(\displaystyle \mbox{the original expres}\mbox{sion. So the relation is proved.}\)


Please reply if you're not understanding the difference, logically, between what you and I did. Thank you!

Thanks for the explanation Stapel! I understand the difference