For every
n
∈
ℕ
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@
we have
:
(
X
−
a
)
∑
i
=
0
n
−
1
a
i
X
n
−
i
−
1
=
X
n
−
a
n
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadIfacqGHsislcaWGHbGaaiykamaaqahabaGaamyyamaaCaaaleqabaGaamyAaaaakiaadIfadaahaaWcbeqaaiaad6gacqGHsislcaWGPbGaeyOeI0IaaGymaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gacqGHsislcaaIXaaaniabggHiLdGccqGH9aqpcaWGybWaaWbaaSqabeaacaWGUbaaaOGaeyOeI0IaamyyamaaCaaaleqabaGaamOBaaaaaaa@4F07@
.
Proof
by induction on
n
:
For
n
=
1
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabg2da9iaaigdaaaa@389D@
we get:
(
X
−
a
)
∑
i
=
0
1
−
1
a
i
X
1
−
i
−
1
=
(
X
−
a
)
⋅
a
0
X
0
=
X
−
a
=
X
1
−
a
1
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadIfacqGHsislcaWGHbGaaiykamaaqahabaGaamyyamaaCaaaleqabaGaamyAaaaakiaadIfadaahaaWcbeqaaiaaigdacqGHsislcaWGPbGaeyOeI0IaaGymaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaaigdacqGHsislcaaIXaaaniabggHiLdGccqGH9aqpcaGGOaGaamiwaiabgkHiTiaadggacaGGPaGaeyyXICTaamyyamaaCaaaleqabaGaaGimaaaakiaadIfadaahaaWcbeqaaiaaicdaaaGccqGH9aqpcaWGybGaeyOeI0Iaamyyaiabg2da9iaadIfadaahaaWcbeqaaiaaigdaaaGccqGHsislcaWGHbWaaWbaaSqabeaacaaIXaaaaaaa@5CDB@
.
Now suppose the equation to be valid for an arbitrary
n
. This implies for the next number
n
+
1
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdaaaa@3879@
:
(
X
−
a
)
∑
i
=
0
n
a
i
X
n
−
i
=
(
X
−
a
)
(
X
∑
i
=
0
n
−
1
a
i
X
n
−
i
−
1
+
a
n
)
=
X
(
X
n
−
a
n
)
+
a
n
(
X
−
a
)
=
X
n
+
1
-
a
n
X
+
a
n
X
−
a
n
+
1
=
X
n
+
1
−
a
n
+
1
.
MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabqGaaaaabaGaaiikaiaadIfacqGHsislcaWGHbGaaiykamaaqahabaGaamyyamaaCaaaleqabaGaamyAaaaakiaadIfadaahaaWcbeqaaiaad6gacqGHsislcaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aaGcbaGaeyypa0JaaiikaiaadIfacqGHsislcaWGHbGaaiykaiaacIcacaWGybWaaabCaeaacaWGHbWaaWbaaSqabeaacaWGPbaaaOGaamiwamaaCaaaleqabaGaamOBaiabgkHiTiaadMgacqGHsislcaaIXaaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaiabgkHiTiaaigdaa0GaeyyeIuoakiabgUcaRiaadggadaahaaWcbeqaaiaad6gaaaGccaGGPaaabaaabaGaeyypa0JaamiwaiaacIcacaWGybWaaWbaaSqabeaacaWGUbaaaOGaeyOeI0IaamyyamaaCaaaleqabaGaamOBaaaakiaacMcacqGHRaWkcaWGHbWaaWbaaSqabeaacaWGUbaaaOGaaiikaiaadIfacqGHsislcaWGHbGaaiykaaqaaaqaaiabg2da9iaadIfadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaOGaeyOeI0IaamyyamaaCaaaleqabaGaamOBaaaakiaadIfacqGHRaWkcaWGHbWaaWbaaSqabeaacaWGUbaaaOGaamiwaiabgkHiTiaadggadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaaGcbaaabaGaeyypa0JaamiwamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaGccqGHsislcaWGHbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaaaaaaaa@887A@