Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 4 Marks

Year: Dec 2013

Step1: Take P(n): $x^n-y^n$ is divisible by x-y

Basis of induction

For n=1

We have

$P (1): x^1 - y^1 = x – y$ is divisible by x – y.

So, P(1) is true.

Step2: Induction step: Assume P(k-1) is true,

That is $x^{k-1} - y^{k-1}$ is divisible by x-y.

$x^{k-1} - y^{k-1} =a(x-y)$

$x^{k-1} = y^{k-1}+a(x-y)$

To prove for n=k

$x^k - y^k$ $=x^{k-1} x - y^{k-1} y \\ =(y^{k-1}+a(x-y))x-y^{k-1} y=y^{k-1} x+a(x-y)x-y^{k-1} y\\ =y^{k-1}(x-y)+ax(x-y)=( y^{k-1}+ax)(x-y)$

That is $x^k - y^k$ is divisible by x-y.

Therefore, P(k) is true.

By the principle of mathematical induction

$x^n-y^n$ is divisible by x-y for all n € N