DEV Community

hwangs12
hwangs12

Posted on

Proof by Induction

Statement

xn−yn=(x−y)(xn−1+xn−2y+⋯+xyn−2+yn−1) x^n - y^n = (x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})

Proof

Suppose n=1:

x−y=(x−y)∗1=x−y x - y = (x-y)*1 = x-y

Suppose the statement is true for all k < n:

(xk−yk)(x+y)=xk+1+xky−xyk−yk+1 \quad (x^k - y^k)(x + y) = x^{k+1} + x^ky - xy^k - y^{k+1}

xk+1−yk+1=(xk−yk)(x+y)−xky+xyk \quad x^{k+1} - y^{k+1} = (x^k - y^k)(x+y)-x^ky+xy^k

xk+1−yk+1=(x−y)(xk−1+xk−2y⋯+xyk−2+yk−1)(x+y)−xy(xk−1+yk−1) \quad x^{k+1} - y^{k+1} = (x-y)(x^{k-1} + x^{k-2}y \cdots + xy^{k-2} + y^{k-1})(x+y)-xy(x^{k-1}+y^{k-1})

xk+1−yk+1=(x−y)(xk−1+xk−2y⋯+xyk−2+yk−1)(x+y)−xy(xk−1−yk−1) \quad x^{k+1} - y^{k+1} = (x-y)(x^{k-1} + x^{k-2}y \cdots + xy^{k-2} + y^{k-1})(x+y)-xy(x^{k-1}-y^{k-1})

xk+1−yk+1=(x−y)(xk−1+xk−2y⋯+xyk−2+yk−1)(x+y)−xy(x−y)(xk−2+xk−3y+⋯+xyk−3+yk−2) \quad x^{k+1} - y^{k+1} = (x-y)(x^{k-1} + x^{k-2}y \cdots + xy^{k-2} + y^{k-1})(x+y)-xy(x-y)(x^{k-2}+x^{k-3}y+\cdots+xy^{k-3}+y^{k-2})

xk+1−yk+1=(x−y)(xk−1+xk−2y⋯+xyk−2+yk−1)(x+y)−(x−y)(xk−1+xk−2y2+⋯+x2yk−2+yk−1) \quad x^{k+1} - y^{k+1} = (x-y)(x^{k-1} + x^{k-2}y \cdots + xy^{k-2} + y^{k-1})(x+y)-(x-y)(x^{k-1}+x^{k-2}y^2+\cdots+x^2y^{k-2}+y^{k-1})

xk+1−yk+1=(x−y)(xk+xk−1y+⋯+x2yk−2+xyk−1+xk−1y+xk−2y2+⋯+xyk−1+yk−xk−1y−xk−2y2−⋯−x2yk−2−xyk−1) \quad x^{k+1} - y^{k+1} = (x-y)(x^k+x^{k-1}y+\cdots+x^2y^{k-2}+xy^{k-1}+x^{k-1}y+x^{k-2}y^2+\cdots+xy^{k-1}+y^k-x^{k-1}y-x^{k-2}y^2-\cdots-x^2y^{k-2}-xy^{k-1})

xk+1−yk+1=(x−y)(xk+xk−1y+⋯+x2yk−2+xyk−1+yk)■ \quad x^{k+1} - y^{k+1} = (x-y)(x^k+x^{k-1}y+\cdots+x^2y^{k-2}+xy^{k-1}+y^k) \blacksquare

Top comments (0)

Read next

tereyaki profile image

Hiring React JS dev

Tere -

oyebobs profile image

What was your win this week?

Adeoye Malumi -

ayush010890 profile image

How to Add Quote of the Day on Blog Post

Ayush Sharma -

carlosalberto profile image

Como conectar Spark e S3 para processamento de arquivos

Carlos Alberto -