5.2. Recursive Sequences and the Principle of Induction


Choosing MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHu6aaWbaaSqabeaacqGHxiIkaaaaaa@3871@ as domain for our sequences has a wide effect mainly due to the well advanced arithmetic and ordering properties that come with the natural numbers. This structure is settled when constructing MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ in set theory. From there we take the following characterization of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ :

Proposition:  
  1. k k=0k=n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolablwriLkabgkDiElaadUgacqGH9aqpcaaIWaGaeyikIOTaam4Aaiabg2da9iaad6gacqGHRaWkcaaIXaaaaa@450C@   for a suitable  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ .
     
  2. Every non-empty subset of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ has a smallest element.
[5.2.1]

That means:

  • Every non-zero natural number is the successor of another natural number.
     
  • Every non-empty collection of natural numbers has a first one.

Both of these properties already support the idea to get every natural number by successive counting starting with 0. The Principle of Induction makes this precise:

Proposition (Principle of Induction):  Let A be an arbitrary subset of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ so that
  • 0A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeaaaa@38ED@
  • nAn+1A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeaaaa@405D@
[5.2.2]
Then A is the whole of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ , i.e.:  A= MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabg2da9iablwriLcaa@3921@ .

Proof:  We proceed indirectly and assume: A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabgcMi5kablwriLcaa@39E2@ . Then the difference \A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHuQaaiixaiaadgeaaaa@38FB@ is a non-empty subset of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ and, following 2. in [5.2.1], has a smallest element, say k\A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolablwriLkaacYfacaWGbbaaaa@3B6F@ . From 0A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeaaaa@38ED@ we conclude that k0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgcMi5kaaicdaaaa@395A@ . According 1. in [5.2.1] we find a number n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ so that k=n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4Aaiabg2da9iaad6gacqGHRaWkcaaIXaaaaa@3A6F@ . Especially we have n<k MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgYda8iaadUgaaaa@38D0@ . As k is the smallest element of  \A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHuQaaiixaiaadgeaaaa@38FB@ we thus know that n is no member of  \A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHuQaaiixaiaadgeaaaa@38FB@ . But that means nA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeaaaa@3926@ and from the second condition in [5.2.2] we can conclude that k=n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4Aaiabg2da9iaad6gacqGHRaWkcaaIXaaaaa@3A6F@ belongs to A.   contradiction!

 
The induction principle is a very effective tool. A whole technique called proof by induction, is based on this principle. We take the proof of a so called summation formula as a first example to demonstrate this technique: Adding the odd intergers from 1 to 2n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGOmaiaad6gacqGHRaWkcaaIXaaaaa@3935@ gives the following results for the different values of n:

n = 0 n = 1 n = 2 n = 3 n = 4 n = 5
1
= 1
1 + 3
= 4
1 + 3 + 5
= 9
1 + 3 + 5 + 7
= 16
1 + 3 + 5 + 7 + 9
= 25
1 + 3 + 5 + 7 + 9 + 11
= 36

Obviously each of the six results is a square number, namely the square of  n + 1, the number of addends! We would gain an enormous advantage, especially for huge numbers, if this would be true for every n. Unfortunately however this assumption could not be proved the customary way because we have to prove infinitely many single assertions. But exactly that is performed by the induction principle.

Example:  For all n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ we have:
 
i=0 n (2i+1) = (n+1) 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiaacMcacqGH9aqpcaGGOaGaamOBaiabgUcaRiaaigdacaGGPaWaaWbaaSqabeaacaaIYaaaaaaa@464E@
[5.2.3]

Proof:  

Our task is, a bit awkwardly shaped, the following: Show that the set

A{ n| i=0 n (2i+1) = (n+1) 2 } MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabg2da9iaacUhacaWGUbGaeyicI4SaeSyfHuQaaiiFamaaqahabaGaaiikaiaaikdacaWGPbGaey4kaSIaaGymaiaacMcaaSqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aOGaeyypa0Jaaiikaiaad6gacqGHRaWkcaaIXaGaaiykamaaCaaaleqabaGaaGOmaaaakiaac2hacqGHckcZcqWIvesPaaa@526F@ ,

i.e. the collection of all natural numbers satisfying [5.2.3] is all of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ . But to that end we only need to check if the two conditions of the induction principle hold for A!

  • 0A: i=0 0 (2i+1) =1= (0+1) 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaGaaiykaaWcbaGaamyAaiabg2da9iaaicdaaeaacaaIWaaaniabggHiLdGccqGH9aqpcaaIXaGaeyypa0JaaiikaiaaicdacqGHRaWkcaaIXaGaaiykamaaCaaaleqabaGaaGOmaaaaaaa@4B5F@
     
  • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@ nA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeaaaa@3926@  means that this n actually satisfies i=0 n (2i+1) = (n+1) 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiaacMcacqGH9aqpcaGGOaGaamOBaiabgUcaRiaaigdacaGGPaWaaWbaaSqabeaacaaIYaaaaaaa@464E@ . To show that n + 1 also belongs to A the equation i=0 n+1 (2i+1 )= (n+1+1) 2 = (n+2) 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gacqGHRaWkcaaIXaaaniabggHiLdGccaGGPaGaeyypa0Jaaiikaiaad6gacqGHRaWkcaaIXaGaey4kaSIaaGymaiaacMcadaahaaWcbeqaaiaaikdaaaGccqGH9aqpcaGGOaGaamOBaiabgUcaRiaaikdacaGGPaWaaWbaaSqabeaacaaIYaaaaaaa@4F6B@ has to be verified:
     
    i=0 n+1 (2i+1) = i=0 n (2i+1) +2(n+1)+1 = (n+1) 2 +2(n+1)+1 = (n+1+1) 2 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabmGaaaqaamaaqahabaGaaiikaiaaikdacaWGPbGaey4kaSIaaGymaiaacMcaaSqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaiabgUcaRiaaigdaa0GaeyyeIuoaaOqaaiabg2da9maaqahabaGaaiikaiaaikdacaWGPbGaey4kaSIaaGymaiaacMcaaSqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aOGaey4kaSIaaGOmaiaacIcacaWGUbGaey4kaSIaaGymaiaacMcacqGHRaWkcaaIXaaabaaabaGaeyypa0Jaaiikaiaad6gacqGHRaWkcaaIXaGaaiykamaaCaaaleqabaGaaGOmaaaakiabgUcaRiaaikdacaGGOaGaamOBaiabgUcaRiaaigdacaGGPaGaey4kaSIaaGymaaqaaaqaaiabg2da9iaacIcacaWGUbGaey4kaSIaaGymaiabgUcaRiaaigdacaGGPaWaaWbaaSqabeaacaaIYaaaaaaaaaa@6957@

    Thus n+1A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdacqGHiiIZcaWGbbaaaa@3AC3@ .

The principle of induction now guarantees: A= MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabg2da9iablwriLcaa@3921@ . In other words our summation formular is actually true for all natural numbers.

Consider:

  • The just performed technique, splitting off the last addend,
     

    i=0 n+1 (2i+1 )= i=0 n (2i+1 )+ i=n+1 n+1 (2i+1 )= i=0 n (2i+1 )+2(n+1)+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gacqGHRaWkcaaIXaaaniabggHiLdGccaGGPaGaeyypa0ZaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiaacMcacqGHRaWkdaaeWbqaaiaacIcacaaIYaGaamyAaiabgUcaRiaaigdaaSqaaiaadMgacqGH9aqpcaWGUbGaey4kaSIaaGymaaqaaiaad6gacqGHRaWkcaaIXaaaniabggHiLdGccaGGPaGaeyypa0ZaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiaacMcacqGHRaWkcaaIYaGaaiikaiaad6gacqGHRaWkcaaIXaGaaiykaiabgUcaRiaaigdaaaa@6F3F@
     
    is the standard trick for sums and related expressions.

  • With proofs by induction it is a valuable advantage that the sentence to be proved - in our example the equation i=0 n+1 (2i+1 )= (n+1+1) 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaGGOaGaaGOmaiaadMgacqGHRaWkcaaIXaaaleaacaWGPbGaeyypa0JaaGimaaqaaiaad6gacqGHRaWkcaaIXaaaniabggHiLdGccaGGPaGaeyypa0Jaaiikaiaad6gacqGHRaWkcaaIXaGaey4kaSIaaGymaiaacMcadaahaaWcbeqaaiaaikdaaaaaaa@4988@ - can be noted just from the start by inserting n + 1 for n.


 

We practise the principle of induction with further summation formulas and other examples. We do this however without the explicit formation of the set A and take the terms 0A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeaaaa@38ED@ resp. nAn+1A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeaaaa@405D@ only as a label for the two steps in a proof by induction:
 

  • 0A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeaaaa@38ED@   for the base step
     
  • nAn+1A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeaaaa@405D@   for the induction step.
     

Proposition (Summation formula for the geometric series):  Let q,q1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCaiabgIGiolabl2riHkaacYcacaWGXbGaeyiyIKRaaGymaaaa@3DFB@ , then every n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ satisfies:
 
i=0 n q i = 1 q n+1 1q MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaacaWGXbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aOGaeyypa0ZaaSaaaeaacaaIXaGaeyOeI0IaamyCamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaaakeaacaaIXaGaeyOeI0IaamyCaaaaaaa@46F5@
[5.2.4]

Proof:  

  • 0A: i=0 0 q i = q 0 =1= 1 q 0+1 1q . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aWaaabCaeaacaWGXbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaaGimaaqdcqGHris5aOGaeyypa0JaamyCamaaCaaaleqabaGaaGimaaaakiabg2da9iaaigdacqGH9aqpdaWcaaqaaiaaigdacqGHsislcaWGXbWaaWbaaSqabeaacaaIWaGaey4kaSIaaGymaaaaaOqaaiaaigdacqGHsislcaWGXbaaaaaa@4EF3@
     
  • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@

    i=0 n+1 q i = i=0 n q i + q n+1 = 1 q n+1 1q + q n+1 = 1 q n+1 +(1q) q n+1 1q = 1 q n+1 + q n+1 q n+2 1q = 1 q n+1+1 1q . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabuGaaaaabaWaaabCaeaacaWGXbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaiabgUcaRiaaigdaa0GaeyyeIuoaaOqaaiabg2da9maaqahabaGaamyCamaaCaaaleqabaGaamyAaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabgUcaRiaadghadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaaGcbaaabaGaeyypa0ZaaSaaaeaacaaIXaGaeyOeI0IaamyCamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaaakeaacaaIXaGaeyOeI0IaamyCaaaacqGHRaWkcaWGXbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaaaOqaaaqaaiabg2da9maalaaabaGaaGymaiabgkHiTiaadghadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaOGaey4kaSIaaiikaiaaigdacqGHsislcaWGXbGaaiykaiaadghadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaaGcbaGaaGymaiabgkHiTiaadghaaaaabaaabaGaeyypa0ZaaSaaaeaacaaIXaGaeyOeI0IaamyCamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaGccqGHRaWkcaWGXbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaakiabgkHiTiaadghadaahaaWcbeqaaiaad6gacqGHRaWkcaaIYaaaaaGcbaGaaGymaiabgkHiTiaadghaaaaabaaabaGaeyypa0ZaaSaaaeaacaaIXaGaeyOeI0IaamyCamaaCaaaleqabaGaamOBaiabgUcaRiaaigdacqGHRaWkcaaIXaaaaaGcbaGaaGymaiabgkHiTiaadghaaaaaaaaa@89A9@

The summation formula for the geometric series playes a very important role in calculus. This is also true for the generalization of common binomial formula which we will present in the next proposition. For the notation we need the binomial coefficients  (T n i )T MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaaaaa@3930@ , for the slightly extensive proof we need two of their properties and a trick called index shift.

Proposition (Generalized Binomial Theorem):  Let a,b MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyaiaacYcacaWGIbGaeyicI4SaeSyhHekaaa@3B5A@ , then
 
(a+b) n = i=0 n (T n i )T a ni b i MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggacqGHRaWkcaWGIbGaaiykamaaCaaaleqabaGaamOBaaaakiabg2da9maaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aaaa@4B2D@
[5.2.5]

holds for every n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ .

Proof:  

  • 0A: (a+b) 0 =1=(T 0 0 )T a 00 b 0 = i=0 0 (T 0 i )T a 0i b i MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aGaaiikaiaadggacqGHRaWkcaWGIbGaaiykamaaCaaaleqabaGaaGimaaaakiabg2da9iaaigdacqGH9aqpcaGGOaqbaeqabiqaaaqaaiaaicdaaeaacaaIWaaaaiaacMcacaWGHbWaaWbaaSqabeaacaaIWaGaeyOeI0IaaGimaaaakiaadkgadaahaaWcbeqaaiaaicdaaaGccqGH9aqpdaaeWbqaaiaacIcafaqabeGabaaabaGaaGimaaqaaiaadMgaaaGaaiykaiaadggadaahaaWcbeqaaiaaicdacqGHsislcaWGPbaaaOGaamOyamaaCaaaleqabaGaamyAaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaaicdaa0GaeyyeIuoaaaa@5902@ .
     
  • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@

    (a+b) n+1 = (a+b) n (a+b) =( i=0 n (T n i )T a ni b i )a+( i=0 n (T n i )T a ni b i )b = i=0 n (T n i )T a n+1i b i + i=0 n (T n i )T a ni b i+1 = i=0 n (T n i )T a n+1i b i + i=1 n+1 (T n i1 )T a n+1i b i =(T n 0 )T a n+10 b 0 + i=1 n (T n i )T a n+1i b i + i=1 n (T n i1 )T a n+1i b i +(T n n )T a 0 b n+1 =(T n 0 )T a n+10 b 0 + i=1 n ((T n i )T+(T n i1 )T) a n+1i b i +(T n n )T a 0 b n+1 =(T n+1 0 )T a n+10 b 0 + i=1 n (T n+1 i )T a n+1i b i +(T n+1 n+1 )T a 0 b n+1 = i=0 n+1 (T n+1 i )T a n+1i b i . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabGGaaaaaaeaacaGGOaGaamyyaiabgUcaRiaadkgacaGGPaWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaaaOqaaiabg2da9iaacIcacaWGHbGaey4kaSIaamOyaiaacMcadaahaaWcbeqaaiaad6gaaaGccaGGOaGaamyyaiabgUcaRiaadkgacaGGPaaabaaabaGaeyypa0JaaiikamaaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aOGaaiykaiaadggacqGHRaWkcaGGOaWaaabCaeaacaGGOaqbaeqabiqaaaqaaiaad6gaaeaacaWGPbaaaiaacMcacaWGHbWaaWbaaSqabeaacaWGUbGaeyOeI0IaamyAaaaakiaadkgadaahaaWcbeqaaiaadMgaaaaabaGaamyAaiabg2da9iaaicdaaeaacaWGUbaaniabggHiLdGccaGGPaGaamOyaaqaaaqaaiabg2da9maaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdacqGHsislcaWGPbaaaOGaamOyamaaCaaaleqabaGaamyAaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabgUcaRmaaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbGaey4kaSIaaGymaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoaaOqaaaqaaiabg2da9maaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdacqGHsislcaWGPbaaaOGaamOyamaaCaaaleqabaGaamyAaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabgUcaRmaaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaiabgkHiTiaaigdaaaGaaiykaiaadggadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaGaeyOeI0IaamyAaaaakiaadkgadaahaaWcbeqaaiaadMgaaaaabaGaamyAaiabg2da9iaaigdaaeaacaWGUbGaey4kaSIaaGymaaqdcqGHris5aaGcbaaabaGaeyypa0JaaiikauaabeqaceaaaeaacaWGUbaabaGaaGimaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdacqGHsislcaaIWaaaaOGaamOyamaaCaaaleqabaGaaGimaaaakiabgUcaRmaaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaamyyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdacqGHsislcaWGPbaaaOGaamOyamaaCaaaleqabaGaamyAaaaaaeaacaWGPbGaeyypa0JaaGymaaqaaiaad6gaa0GaeyyeIuoakiabgUcaRmaaqahabaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaiabgkHiTiaaigdaaaGaaiykaiaadggadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaGaeyOeI0IaamyAaaaakiaadkgadaahaaWcbeqaaiaadMgaaaaabaGaamyAaiabg2da9iaaigdaaeaacaWGUbaaniabggHiLdGccqGHRaWkcaGGOaqbaeqabiqaaaqaaiaad6gaaeaacaWGUbaaaiaacMcacaWGHbWaaWbaaSqabeaacaaIWaaaaOGaamOyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaaakeaaaeaacqGH9aqpcaGGOaqbaeqabiqaaaqaaiaad6gaaeaacaaIWaaaaiaacMcacaWGHbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaiabgkHiTiaaicdaaaGccaWGIbWaaWbaaSqabeaacaaIWaaaaOGaey4kaSYaaabCaeaacaGGOaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaey4kaSIaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaiabgkHiTiaaigdaaaGaaiykaiaacMcacaWGHbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIXaaabaGaamOBaaqdcqGHris5aOGaey4kaSIaaiikauaabeqaceaaaeaacaWGUbaabaGaamOBaaaacaGGPaGaamyyamaaCaaaleqabaGaaGimaaaakiaadkgadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaaaaaGcbaaabaGaeyypa0JaaiikauaabeqaceaaaeaacaWGUbGaey4kaSIaaGymaaqaaiaaicdaaaGaaiykaiaadggadaahaaWcbeqaaiaad6gacqGHRaWkcaaIXaGaeyOeI0IaaGimaaaakiaadkgadaahaaWcbeqaaiaaicdaaaGccqGHRaWkdaaeWbqaaiaacIcafaqabeGabaaabaGaamOBaiabgUcaRiaaigdaaeaacaWGPbaaaiaacMcacaWGHbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIXaaabaGaamOBaaqdcqGHris5aOGaey4kaSIaaiikauaabeqaceaaaeaacaWGUbGaey4kaSIaaGymaaqaaiaad6gacqGHRaWkcaaIXaaaaiaacMcacaWGHbWaaWbaaSqabeaacaaIWaaaaOGaamOyamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaaakeaaaeaacqGH9aqpdaaeWbqaaiaacIcafaqabeGabaaabaGaamOBaiabgUcaRiaaigdaaeaacaWGPbaaaiaacMcacaWGHbWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaiabgkHiTiaadMgaaaGccaWGIbWaaWbaaSqabeaacaWGPbaaaaqaaiaadMgacqGH9aqpcaaIWaaabaGaamOBaiabgUcaRiaaigdaa0GaeyyeIuoaaaaaaa@5EFD@

Summation formulas are by far not the only sentences to be proved by induction. The following example deals with an inequality.

Proposition (Bernoulli Inequality):  For every real number x1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiEaiabgwMiZkabgkHiTiaaigdaaaa@3A54@ and any n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ we have:

(1+x) n 1+nx MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykamaaCaaaleqabaGaamOBaaaakiabgwMiZkaaigdacqGHRaWkcaWGUbGaamiEaaaa@4059@
[5.2.6]

Proof:  

  • 0A: (1+x) 0 =11=1+0x MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykamaaCaaaleqabaGaaGimaaaakiabg2da9iaaigdacqGHLjYScaaIXaGaeyypa0JaaGymaiabgUcaRiaaicdacqGHflY1caWG4baaaa@4975@ .

  • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@ Assume the inequality (1+x) n 1+nx MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykamaaCaaaleqabaGaamOBaaaakiabgwMiZkaaigdacqGHRaWkcaWGUbGaamiEaaaa@4059@ is already valid. Multiplying with the (due to x1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiEaiabgwMiZkabgkHiTiaaigdaaaa@3A54@ ) positive number 1+x MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiabgUcaRiaadIhaaaa@3883@ gives:

    (1+x) n (1+x)(1+nx)(1+x) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykamaaCaaaleqabaGaamOBaaaakiaacIcacaaIXaGaey4kaSIaamiEaiaacMcacqGHLjYScaGGOaGaaGymaiabgUcaRiaad6gacaWG4bGaaiykaiaacIcacaaIXaGaey4kaSIaamiEaiaacMcaaaa@4998@ .

    Thus we can argue as follows::

    (1+x) n+1 = (1+x) n (1+x) (1+nx)(1+x) =1+nx+x+n x 2 1+nx+x,   note that n x 2 0 =1+(n+1)x. MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabuGaaaaabaGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykamaaCaaaleqabaGaamOBaiabgUcaRiaaigdaaaaakeaacqGH9aqpcaGGOaGaaGymaiabgUcaRiaadIhacaGGPaWaaWbaaSqabeaacaWGUbaaaOGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykaaqaaaqaaiabgwMiZkaacIcacaaIXaGaey4kaSIaamOBaiaadIhacaGGPaGaaiikaiaaigdacqGHRaWkcaWG4bGaaiykaaqaaaqaaiabg2da9iaaigdacqGHRaWkcaWGUbGaamiEaiabgUcaRiaadIhacqGHRaWkcaWGUbGaamiEamaaCaaaleqabaGaaGOmaaaaaOqaaaqaaiabgwMiZkaaigdacqGHRaWkcaWGUbGaamiEaiabgUcaRiaadIhacaqGKbGaaeyzaiaab6gacaqGUbGaamOBaiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHLjYScaaIWaaabaaabaGaeyypa0JaaGymaiabgUcaRiaacIcacaWGUbGaey4kaSIaaGymaiaacMcacaWG4bGaaeOlaaaaaaa@7427@

The initial value 0 used with principle of induction is determind by the set MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ . However we can modify the induction principle so that any integer k gets the option for the initial value:

Proposition:  Let k MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolablssiIcaa@39D5@ and A be any subset of k MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSijHi6aaWbaaSqabeaacqGHLjYScaWGRbaaaaaa@3A44@ so that
  • kA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolaadgeaaaa@3923@
  • nAn+1A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeaaaa@405D@
[5.2.7]
then we have: A= k MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabg2da9iablssiIoaaCaaaleqabaGaeyyzImRaam4Aaaaaaaa@3C10@ .

Proof:  Let us set A'{ik|iA} MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiaacEcacqGH9aqpcaGG7bGaamyAaiabgkHiTiaadUgacaGG8bGaamyAaiabgIGiolaadgeacaGG9baaaa@4163@ . A' then is a subset of  MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyfHukaaa@3755@ containing 0 and with every n the successor n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdaaaa@3879@ as well. From the induction principle we have A'= MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiaacEcacqGH9aqpcqWIvesPaaa@39CC@ and thus A= k MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqaiabg2da9iablssiIoaaCaaaleqabaGaeyyzImRaam4Aaaaaaaa@3C10@ .


 

Very close related to the induction principle is a certain construction method, often used with sequences, the so called definition by recursion. We need two steps for a sequence ( a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3951@ to be constructed in this way: The initial step is to fix a value for the first sequence member a 1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaaaaa@37B6@ . The second step is to introduce a general method to calculate any sequence member a n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaaaaa@398B@ from its predecessor a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaaaaa@37EE@ . As an example the sequence ( a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3951@ could be constructed by the statement:

a 1 1 a n+1 2 a n . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaaikdacaWGHbWaaSbaaSqaaiaad6gaaeqaaaaa@42A2@

From the recursion formula we see that every new sequence member is twice its predecessor. So we can calculate the sequence members one after the other:

( a n )=(1,2,4,8,16,32,). MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaGaeyypa0JaaiikaiaaigdacaGGSaGaaGOmaiaacYcacaaI0aGaaiilaiaaiIdacaGGSaGaaGymaiaaiAdacaGGSaGaaG4maiaaikdacaGGSaGaeSOjGSKaaiykaaaa@46DD@

The following proposition introduces the Principle of Recursion.

Proposition (Principle of Recursion):  For any cA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabgIGiolaadgeaaaa@391B@ and any function  f: ×AA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacQdacqWIvesPdaahaaWcbeqaaiabgEHiQaaakiabgEna0kaadgeacqGHsgIRcaWGbbaaaa@3FB4@ the statement

a 1 c a n+1 f(n, a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaadogacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadAgacaGGOaGaamOBaiaacYcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiykaaaa@4604@
[5.2.8]

defines a sequence in A.

Proof:  We need to show that [5.2.8] constitutes a function  a: A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyaiaacQdacqWIvesPdaahaaWcbeqaaiabgEHiQaaakiabgkziUkaadgeaaaa@3CD2@ . First we show that every n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@  has got an image in A. We set

D{n |there is an element   a n A   according to [5.2.8]} MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiraiabg2da9iaacUhacaWGUbGaeyicI4SaeSyfHu6aaWbaaSqabeaacqGHxiIkaaGccaGG8bGaaeyzaiaabohacaqGGaGaae4zaiaabMgacaqGIbGaaeiDaiaabccacaqGLbGaaeyAaiaab6gacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyicI4SaamyqaiaabEgacaqGLbGaaeyBaiaabsoacaqGFdGaaeiiaiaabUfacaqG1aGaaeOlaiaabkdacaqGUaGaaeioaiaab2facaGG9baaaa@592B@ .

As a 1 A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabgIGiolaadgeaaaa@3A0A@ is guaranted by the premise we have 1D MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiabgIGiolaadseaaaa@38F1@ . Now if nD MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadseaaaa@3929@ , i.e. a n A MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabgIGiolaadgeaaaa@3A42@ the recursion formula assigns an element of A to the successor n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdaaaa@3879@ , but that means n+1D MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdacqGHiiIZcaWGebaaaa@3AC6@ . Thus we have D= MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiraiabg2da9iablwriLoaaCaaaleqabaGaey4fIOcaaaaa@3A40@ according to the (generalized) induction principle.

Next we show that there is only one image for each n, applying the induction principle again: For the set

E{n |there is only one element   a n A  according to [5.2.8]} MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyraiabg2da9iaacUhacaWGUbGaeyicI4SaeSyfHu6aaWbaaSqabeaacqGHxiIkaaGccaGG8bGaaeyzaiaabohacaqGGaGaae4zaiaabMgacaqGIbGaaeiDaiaabccacaqGNbGaaeyzaiaab6gacaqGHbGaaeyDaiaabccacaqGLbGaaeyAaiaab6gacaqGLbGaaeOBaiaabccacaqGxbGaaeyzaiaabkhacaqG0bGaamyyamaaBaaaleaacaWGUbaabeaakiabgIGiolaadgeacaqGNbGaaeyzaiaab2gacaqGKdGaae43aiaabccacaqGBbGaaeynaiaab6cacaqGYaGaaeOlaiaabIdacaqGDbGaaiyFaaaa@6498@

we have: 1E MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiabgIGiolaadweaaaa@38F2@ , because there is no n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLoaaCaaaleqabaGaey4fIOcaaaaa@3AE8@ such that 1=n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiabg2da9iaad6gacqGHRaWkcaaIXaaaaa@3A3A@ , so that there is no assignment in [5.2.8] except for a 1 =c MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaadogaaaa@39AE@ . Now let nE MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadweaaaa@392A@ , thus a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaaaaa@37EE@ is uniquely determined and so is   f(n, a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacIcacaWGUbGaaiilaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3BDF@ (because  f is a function!). Finally n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdaaaa@3879@ has only one predecessor, namely n. From all that we conclude that a n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaaaaa@398B@ is uniquely determined, thus n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgUcaRiaaigdaaaa@3879@ also belongs to E which completes our induction and we have E= MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyraiabg2da9iablwriLoaaCaaaleqabaGaey4fIOcaaaaa@3A41@ .

Consider:

  • We rarely use the explicit data c and  f  to define a sequence recursively. It is common to note them just the way we did in our introductory example. Either notion however can be translated into the other. E.g. the statement   a 1 =1 a n+1 =2 a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaaikdacaWGHbWaaSbaaSqaaiaad6gaaeqaaaaa@42A2@   turns into:

    c=1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2da9iaaigdaaaa@3892@ and  f: × MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacQdacqWIvesPdaahaaWcbeqaaiabgEHiQaaakiabgEna0kabl2riHkabgkziUkabl2riHcaa@4108@   given by  f(n,x)=2x MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacIcacaWGUbGaaiilaiaadIhacaGGPaGaeyypa0JaaGOmaiaadIhaaaa@3D8C@ .

    Vice versa the data, let's say  c=0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2da9iaaicdaaaa@3891@ and  f: × MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacQdacqWIvesPdaahaaWcbeqaaiabgEHiQaaakiabgEna0kabl2riHkabgkziUkabl2riHcaa@4108@   given by  f(n,x)=n+x MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacIcacaWGUbGaaiilaiaadIhacaGGPaGaeyypa0JaamOBaiabgUcaRiaadIhaaaa@3EA5@ , translate to

    a 1 =0 a n+1 =n+ a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaicdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaad6gacqGHRaWkcaWGHbWaaSbaaSqaaiaad6gaaeqaaaaa@43BA@ .
     

  • As with the induction principle and with the sequences, the principle of recursion is extendable to functions of the type  f: k ×AA MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacQdacqWIKeIOdaahaaWcbeqaaiabgwMiZkaadUgaaaGccqGHxdaTcaWGbbGaeyOKH4Qaamyqaaaa@4187@ .
     

The real advantage of recursive sequences lies in their ability to reflect dynamic situations. Let's say a certain species of bacteria needs one hour to double its stock. Starting with one bacterium we can perfectly calculate the number a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaaaaa@37EE@ of bacteria living at the beginning of the der n-th hour by our initial recursive sequence.

As a clear disadvantage with recursive sequences we see the effort that is needed to calculate sequence members far from the start. To get e.g. the size of the bacteria population when 100 hours are over you need to calculate separately 100 sequence members before!

We practise the principle of recursion with some examples. Note that changing only the first sequence member could result in a complete different sequence.

Example:  

  • a 1 2 a n+1 3 a n 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaikdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaaiodacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyOeI0IaaGOmaaaa@4457@   gives the sequence  (2,4,10,28,82,) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaikdacaGGSaGaaGinaiaacYcacaaIXaGaaGimaiaacYcacaaIYaGaaGioaiaacYcacaaI4aGaaGOmaiaacYcacqWIMaYscaGGPaaaaa@41BF@  , because

    a 2 =3 a 1 2=322=4 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIYaaabeaakiabg2da9iaaiodacaWGHbWaaSbaaSqaaiaaigdaaeqaaOGaeyOeI0IaaGOmaiabg2da9iaaiodacqGHflY1caaIYaGaeyOeI0IaaGOmaiabg2da9iaaisdaaaa@453A@ ,

    a 3 =3 a 2 2=342=10 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIZaaabeaakiabg2da9iaaiodacaWGHbWaaSbaaSqaaiaaikdaaeqaaOGaeyOeI0IaaGOmaiabg2da9iaaiodacqGHflY1caaI0aGaeyOeI0IaaGOmaiabg2da9iaaigdacaaIWaaaaa@45F5@ ,

    a 4 =3 a 3 2=3102=28 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaI0aaabeaakiabg2da9iaaiodacaWGHbWaaSbaaSqaaiaaiodaaeqaaOGaeyOeI0IaaGOmaiabg2da9iaaiodacqGHflY1caaIXaGaaGimaiabgkHiTiaaikdacqGH9aqpcaaIYaGaaGioaiablAcilbaa@47D9@

  • a 1 1 a n+1 3 a n 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaaiodacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyOeI0IaaGOmaaaa@4456@   gives the sequence  (1,1,1,1,1,1,) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacaGGSaGaaGymaiaacYcacaaIXaGaaiilaiaaigdacaGGSaGaaGymaiaacYcacaaIXaGaaiilaiablAciljaacMcaaaa@40E6@  .

  • a 1 1 2 a n+1 1 a n +1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9maalaaabaGaaGymaaqaaiaaikdaaaGaey4jIKTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpdaWcaaqaaiaaigdaaeaacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaaGymaaaaaaa@4524@   gives the sequence  ( 1 2 , 2 3 , 3 5 , 5 8 , 8 13 ,) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikamaalaaabaGaaGymaaqaaiaaikdaaaGaaiilamaalaaabaGaaGOmaaqaaiaaiodaaaGaaiilamaalaaabaGaaG4maaqaaiaaiwdaaaGaaiilamaalaaabaGaaGynaaqaaiaaiIdaaaGaaiilamaalaaabaGaaGioaaqaaiaaigdacaaIZaaaaiaacYcacqWIMaYscaGGPaaaaa@444B@  .
     
  • a 0 1 a n+1 a n (n+1) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHflY1caGGOaGaamOBaiabgUcaRiaaigdacaGGPaaaaa@4822@   produces the sequence of factorials:

    (1,1,2,6,24,120,720,5.040,) n0 = (n!) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacaGGSaGaaGymaiaacYcacaaIYaGaaiilaiaaiAdacaGGSaGaaGOmaiaaisdacaGGSaGaaGymaiaaikdacaaIWaGaaiilaiaaiEdacaaIYaGaaGimaiaacYcacaaI1aGaaiOlaiaaicdacaaI0aGaaGimaiaacYcacqWIMaYscaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGUbGaaiyiaiaacMcadaWgaaWcbaGaamOBaiabgwMiZkaaicdaaeqaaaaa@559A@  .

Two special recursive sequences get names of their own.

Definition:  Let  c,d,q MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiaacYcacaWGKbGaaiilaiaadghacqGHiiIZcqWIDesOaaa@3D04@ . A recursive sequence ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@ of the shape

  • a 0 c a n+1 a n +d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaakiabg2da9iaadogacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaWGKbaaaa@43E7@   is called arithmetic.
     
[5.2.9]
  • a 0 c a n+1 a n q MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaakiabg2da9iaadogacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHflY1caWGXbaaaa@455C@   is called geometric.
     
[5.2.10]

Consider:

  • The new sequence members of an arithmetic sequence are calculated by adding the constant addend d.

    The new sequence members of a geometric sequence are calculated by multiplying the constant factor q.
     

Proposition:  

  1. ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is arithmetic

    MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HSnaaa@3845@ there is a  d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamizaiabgIGiolabl2riHcaa@39C6@ , such that ( a n ) n0 = ( a 0 +nd) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaey4kaSIaamOBaiaadsgacaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@478C@  .
     

[5.2.11]
 
  1. ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is geometric

    MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HSnaaa@3845@ there is a  q MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCaiabgIGiolabl2riHcaa@39D3@ , such that ( a n ) n0 = ( a 0 q n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaeyyXICTaamyCamaaCaaaleqabaGaamOBaaaakiaacMcadaWgaaWcbaGaamOBaiabgwMiZkaaicdaaeqaaaaa@4938@  .

[5.2.12]

Proof:  We concentrate on 1. The second assertion is just a multiplicative version of the first one. We split the equivalence into two parts.

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyO0H4naaa@3846@ ":  Let c and d be reals such that

a 0 =c a n+1 = a n +d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaakiabg2da9iaadogacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaWGKbaaaa@43E7@ .

Now we show by induction:  a n = a 0 +nd MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHRaWkcaWGUbGaamizaaaa@3D92@   for all n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolablwriLcaa@39CC@ .

  • 0A: a 0 = a 0 +0d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaaIWaaabeaakiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHRaWkcaaIWaGaeyyXICTaamizaaaa@432C@ .

  • nAn+1A: a n+1 = a n +d= a 0 +nd+d= a 0 +(n+1)d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamizaiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHRaWkcaWGUbGaamizaiabgUcaRiaadsgacqGH9aqpcaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaey4kaSIaaiikaiaad6gacqGHRaWkcaaIXaGaaiykaiaadsgaaaa@599C@ .

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi0HWnaaa@3842@ ":  Setting

b 0 a 0 b n+1 b n +d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOyamaaBaaaleaacaaIWaaabeaakiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHNis2caWGIbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadkgadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaWGKbaaaa@44D8@ ,

gives an arithmetic sequence ( b n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF1@ that satisfies the equality ( b n ) n0 = ( b 0 +nd) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGIbWaaSbaaSqaaiaaicdaaeqaaOGaey4kaSIaamOBaiaadsgacaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@478E@ as demonstrated just before. From that we have:

( a n ) n0 = ( a 0 +nd) n0 = ( b 0 +nd) n0 = ( b n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaey4kaSIaamOBaiaadsgacaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGIbWaaSbaaSqaaiaaicdaaeqaaOGaey4kaSIaamOBaiaadsgacaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGIbWaaSbaaSqaaiaad6gaaeqaaOGaaiykamaaBaaaleaacaWGUbGaeyyzImRaaGimaaqabaaaaa@5A41@  ,

so that  ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   coincides with an arithmetic sequence and thus is arithmetic itself.

Arithmetic and geometric sequences show are some interesting properties.

  • As a n+1 = a n +d a n+1 a n =d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamizaiabgsDiBlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyOeI0IaamyyamaaBaaaleaacaWGUbaabeaakiabg2da9iaadsgaaaa@4968@ , the difference of two consecutive members of an arithmetic sequence is a constant.:

    ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is arithmetic a n+1 a n =d   for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HSTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGHsislcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyypa0JaamizaiaabAgacaqG8dGaaeOCaiaabccacaqGHbGaaeiBaiaabYgacaqGLbGaamOBaiabgIGiolablwriLcaa@4C69@ .

    Below we show: The members of an arithmetic sequence are the arithmetic mean of their neighbours.

  • As a n+1 = a n q a n+1 a n =q MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyyXICTaamyCaiabgsDiBpaalaaabaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaaakeaacaWGHbWaaSbaaSqaaiaad6gaaeqaaaaakiabg2da9iaadghaaaa@4A0D@ the quotient of two consecutive members of geometric sequence in 0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHe6aaWbaaSqabeaacqGHGjsUcaaIWaaaaaaa@3A07@ a constant:

    ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is geometric a n+1 a n =q   for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HS9aaSaaaeaacaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaaaOqaaiaadggadaWgaaWcbaGaamOBaaqabaaaaOGaeyypa0JaamyCaiaabAgacaqG8dGaaeOCaiaabccacaqGHbGaaeiBaiaabYgacaqGLbGaamOBaiabgIGiolablwriLcaa@4B99@ .

    Next we show: The absolute value of a member of a geometric sequence is the geometric mean of its neighbours.


     

Proposition:  

  1. ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is arithmetic a n+1 = a n + a n+2 2    for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HSTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpdaWcaaqaaiaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIYaaabeaaaOqaaiaaikdaaaGaaeOzaiaabYpacaqGYbGaaeiiaiaabggacaqGSbGaaeiBaiaabwgacaWGUbGaeyicI4SaeSyfHukaaa@4FEE@
     
[5.2.13]
 
  1. ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@   is geometric

    a n a n+2 0| a n+1 |= a n a n+2    for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi1HSTaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaikdaaeqaaOGaeyyzImRaaGimaiabgEIizlaacYhacaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiaacYhacqGH9aqpdaGcaaqaaiaadggadaWgaaWcbaGaamOBaaqabaGccqGHflY1caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIYaaabeaaaeqaaOGaaeOzaiaabYpacaqGYbGaaeiiaiaabggacaqGSbGaaeiBaiaabwgacaWGUbGaeyicI4SaeSyfHukaaa@5ECE@

[5.2.14]

Proof:  
1.  

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyO0H4naaa@3846@ ":  We employ the recursion formula  a n+1 = a n +d MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamizaaaa@3E75@   twice:

a n + a n+2 2 = a n + a n+1 +d 2 = a n +d+ a n+1 2 = a n+1 + a n+1 2 = a n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGOmaaqabaaakeaacaaIYaaaaiabg2da9maalaaabaGaamyyamaaBaaaleaacaWGUbaabeaakiabgUcaRiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaey4kaSIaamizaaqaaiaaikdaaaGaeyypa0ZaaSaaaeaacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamizaiabgUcaRiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaaGcbaGaaGOmaaaacqGH9aqpdaWcaaqaaiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaey4kaSIaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaaakeaacaaIYaaaaiabg2da9iaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaaaa@607B@ .

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi0HWnaaa@3842@ ":  We show by induction

a n+1 = a n + a 1 a 0    for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaey4kaSIaamyyamaaBaaaleaacaaIXaaabeaakiabgkHiTiaadggadaWgaaWcbaGaaGimaaqabaGccaqGMbGaaei=aiaabkhacaqGGaGaaeyyaiaabYgacaqGSbGaaeyzaiaad6gacqGHiiIZcqWIvesPaaa@4DB3@ .

Thus ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@ is represented as an arithmetic sequence with c= a 0  and d= a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccaqG1bGaaeOBaiaabsgacaWGKbGaeyypa0JaamyyamaaBaaaleaacaaIXaaabeaakiabgkHiTiaadggadaWgaaWcbaGaaGimaaqabaaaaa@42FC@

  • 0A: a 1 = a 0 + a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHRaWkcaWGHbWaaSbaaSqaaiaaigdaaeqaaOGaeyOeI0IaamyyamaaBaaaleaacaaIWaaabeaaaaa@43D0@

  • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@ First we have from [5.2.13]: 2 a n+1 = a n + a n+2 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGOmaiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyypa0JaamyyamaaBaaaleaacaWGUbaabeaakiabgUcaRiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaikdaaeqaaaaa@41EB@ This allows the following equation:

    a n+2 =2 a n+1 a n =2 a n +2( a 1 a 0 ) a n =( a n + a 1 a 0 )+ a 1 a 0 = a n+1 + a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabqGaaaaabaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGOmaaqabaaakeaacqGH9aqpcaaIYaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGHsislcaWGHbWaaSbaaSqaaiaad6gaaeqaaaGcbaaabaGaeyypa0JaaGOmaiaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaaIYaGaaiikaiaadggadaWgaaWcbaGaaGymaaqabaGccqGHsislcaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaaiykaiabgkHiTiaadggadaWgaaWcbaGaamOBaaqabaaakeaaaeaacqGH9aqpcaGGOaGaamyyamaaBaaaleaacaWGUbaabeaakiabgUcaRiaadggadaWgaaWcbaGaaGymaaqabaGccqGHsislcaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaaiykaiabgUcaRiaadggadaWgaaWcbaGaaGymaaqabaGccqGHsislcaWGHbWaaSbaaSqaaiaaicdaaeqaaaGcbaaabaGaeyypa0JaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGHRaWkcaWGHbWaaSbaaSqaaiaaigdaaeqaaOGaeyOeI0IaamyyamaaBaaaleaacaaIWaaabeaaaaaaaa@69FD@
2.

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyO0H4naaa@3846@ ":  We proceed as we did in 1., also employing the recursion formula twice:

a n a n+2 = a n a n+1 q= a n q a n+1 = a n+1 a n+1 = a n+1 .2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaikdaaeqaaOGaeyypa0JaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyyXICTaamyCaiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHflY1caWGXbGaeyyXICTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyypa0JaamyyamaaDaaaleaacaWGUbGaey4kaSIaaGymaaqaaiaaikdaaaaaaa@6692@ .

As squares are positive we have a n a n+2 0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaikdaaeqaaOGaeyyzImRaaGimaaaa@406F@ as a first conclusion. The remainder of the assertion now follows when we extract the root.

" MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyi0HWnaaa@3842@ ":  For the proof of this direction we have to consider two cases:

  • a 1 =0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaicdaaaa@3980@ .  Using | a n+1 |= a n a n+2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiiFaiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaaiiFaiabg2da9maakaaabaGaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadggadaWgaaWcbaGaamOBaiabgUcaRiaaikdaaeqaaaqabaaaaa@44A7@ we can show by induction: a n =0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabg2da9iaaicdaaaa@39B8@ for all n1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgwMiZkaaigdaaaa@395D@ . Thus  ( a n ) n0 = ( a 0 ,0,0,0,) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaakiabg2da9iaacIcacaWGHbWaaSbaaSqaaiaaicdaaeqaaOGaaiilaiaaicdacaGGSaGaaGimaiaacYcacaaIWaGaaiilaiablAciljaacMcadaWgaaWcbaGaamOBaiabgwMiZkaaicdaaeqaaaaa@4ADE@   is a geometric sequence with q=0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCaiabg2da9iaaicdaaaa@389F@ .

  • a 1 0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabgcMi5kaaicdaaaa@3A41@ . Now an inductive argument gives: a n 0  for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaakiabgcMi5kaaicdacaqGMbGaaei=aiaabkhacaqGGaGaaeyyaiaabYgacaqGSbGaaeyzaiaad6gacqGHiiIZcqWIvesPaaa@4606@ . From this we show

    a n+1 = a n a 1 a 0    for all  n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyyXIC9aaSaaaeaacaWGHbWaaSbaaSqaaiaaigdaaeqaaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaaaaGccaqGMbGaaei=aiaabkhacaqGGaGaaeyyaiaabYgacaqGSbGaaeyzaiaad6gacqGHiiIZcqWIvesPaaa@4E3E@ ,

    just the same way we did in 1., so that ( a n ) n0 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaWaaSbaaSqaaiaad6gacqGHLjYScaaIWaaabeaaaaa@3CF0@ is a geometric sequence with  c= a 0 q= a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHNis2caWGXbGaeyypa0ZaaSaaaeaacaWGHbWaaSbaaSqaaiaaigdaaeqaaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaaaaaaaa@410A@

    • 0A: a 1 = a 0 a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaaGimaaqabaGccqGHflY1daWcaaqaaiaadggadaWgaaWcbaGaaGymaaqabaaakeaacaWGHbWaaSbaaSqaaiaaicdaaeqaaaaaaaa@445B@

    • nAn+1A: MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aaaaa@411B@ From [5.2.14] we get:  a n+1 .2 = a n a n+2 , MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaDaaaleaacaWGUbGaey4kaSIaaGymaaqaaiaaikdaaaGccqGH9aqpcaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaeyyXICTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGOmaaqabaaaaa@4354@   thus:

      a n+2 = a n+1 .2 a n = a n+1 a n a n+1 = a n+1 a n a n a 1 a 0 = a n+1 a 1 a 0 . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabqGaaaaabaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGOmaaqabaaakeaacqGH9aqpdaWcaaqaaiaadggadaqhaaWcbaGaamOBaiabgUcaRiaaigdaaeaacaaIYaaaaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaaaaaakeaaaeaacqGH9aqpdaWcaaqaaiaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaaGcbaGaamyyamaaBaaaleaacaWGUbaabeaaaaGccqGHflY1caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaaaOqaaaqaaiabg2da9maalaaabaGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaaakeaacaWGHbWaaSbaaSqaaiaad6gaaeqaaaaakiabgwSixlaadggadaWgaaWcbaGaamOBaaqabaGccqGHflY1daWcaaqaaiaadggadaWgaaWcbaGaaGymaaqabaaakeaacaWGHbWaaSbaaSqaaiaaicdaaeqaaaaaaOqaaaqaaiabg2da9iaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyyXIC9aaSaaaeaacaWGHbWaaSbaaSqaaiaaigdaaeqaaaGcbaGaamyyamaaBaaaleaacaaIWaaabeaaaaaaaaaa@69E0@

The next to last proposition touched an intersting, but often difficult problem: Does every recursive sequence allow a non-recursive representation? And if so, is there a general procedure for the transcription? It is very unlikely to find a solution for such a general problem, but from the arithmetic and geometric sequences we know that single solutions are possible. So we have to study a given sequence individually to get an idea for a suitable formula. Whatever way a result was found, the principle of induction is the standard tool for its verification.

Example:  Let  ( a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3951@ be the recursive sequence given by

a 1 1 2 a n+1 a n +1 2 , MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9maalaaabaGaaGymaaqaaiaaikdaaaGaey4jIKTaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpdaWcaaqaaiaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaaIXaaabaGaaGOmaaaaaaa@4525@

i.e. ( a n )=( 1 2 , 3 4 , 7 8 , 15 16 ,) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaGaeyypa0JaaiikamaalaaabaGaaGymaaqaaiaaikdaaaGaaiilamaalaaabaGaaG4maaqaaiaaisdaaaGaaiilamaalaaabaGaaG4naaqaaiaaiIdaaaGaaiilamaalaaabaGaaGymaiaaiwdaaeaacaaIXaGaaGOnaaaacaGGSaGaeSOjGSKaaiykaaaa@473C@ . It is quite obvious that the denominators represent the powers of 2 and that each numerator is one unit less the denominator. Thus we have the idea:

( a n )=( 2 n 1 2 n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaGaeyypa0JaaiikamaalaaabaGaaGOmamaaCaaaleqabaGaamOBaaaakiabgkHiTiaaigdaaeaacaaIYaWaaWbaaSqabeaacaWGUbaaaaaakiaacMcaaaa@4134@

Proof by induction:  

  • 1A: a 1 = 1 2 = 2 1 1 2 1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9maalaaabaGaaGymaaqaaiaaikdaaaGaeyypa0ZaaSaaaeaacaaIYaWaaWbaaSqabeaacaaIXaaaaOGaeyOeI0IaaGymaaqaaiaaikdadaahaaWcbeqaaiaaigdaaaaaaaaa@4420@

  • nAn+1A: a n+1 = a n +1 2 = 2 n 1 2 n +1 2 = 2 n 1+ 2 n 2 2 n = 2 n+1 1 2 n+1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgIGiolaadgeacqGHshI3caWGUbGaey4kaSIaaGymaiabgIGiolaadgeacaGG6aGaamyyamaaBaaaleaacaWGUbGaey4kaSIaaGymaaqabaGccqGH9aqpdaWcaaqaaiaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaaIXaaabaGaaGOmaaaacqGH9aqpdaWcaaqaamaalaaabaGaaGOmamaaCaaaleqabaGaamOBaaaakiabgkHiTiaaigdaaeaacaaIYaWaaWbaaSqabeaacaWGUbaaaaaakiabgUcaRiaaigdaaeaacaaIYaaaaiabg2da9maalaaabaGaaGOmamaaCaaaleqabaGaamOBaaaakiabgkHiTiaaigdacqGHRaWkcaaIYaWaaWbaaSqabeaacaWGUbaaaaGcbaGaaGOmaiabgwSixlaaikdadaahaaWcbeqaaiaad6gaaaaaaOGaeyypa0ZaaSaaaeaacaaIYaWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaakiabgkHiTiaaigdaaeaacaaIYaWaaWbaaSqabeaacaWGUbGaey4kaSIaaGymaaaaaaaaaa@694A@


 

The principle of recursion allows extensions in a varying manner. We could e.g. introduce two stage recursions: We provide the first two sequence members a 1 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaaaaa@37B6@ und a 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIYaaabeaaaaa@37B7@ and thus can use two predecessors when calculating further members.

Example:  The recursive sequence given by

a 1 1, a 2 1 a n+2 a n+1 + a n MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaigdacaGGSaGaamyyamaaBaaaleaacaaIYaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIYaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaey4kaSIaamyyamaaBaaaleaacaWGUbaabeaaaaa@4ABE@
[5.2.15]

is called Fibonacci sequence. Her members are calculated by adding the first two predecessors, so that the Fibonacci numbers start like this:

1,1,2,3,5,8,13,21,34,55, MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiaacYcacaaIXaGaaiilaiaaikdacaGGSaGaaG4maiaacYcacaaI1aGaaiilaiaaiIdacaGGSaGaaGymaiaaiodacaGGSaGaaGOmaiaaigdacaGGSaGaaG4maiaaisdacaGGSaGaaGynaiaaiwdacaGGSaGaeSOjGSeaaa@4843@ .

Another option is to consider recursive sequences in 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHe6aaWbaaSqabeaacaaIYaaaaaaa@3842@ .

Example:  If the recursive sequence (( a n , b n )) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaacIcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaGaaiykaaaa@3D6A@ is given by

( a 1 , b 1 )(2,1)( a n+1 , b n+1 )( a n + b n , a n b n ), MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamOyamaaBaaaleaacaaIXaaabeaakiaacMcacqGH9aqpcaGGOaGaaGOmaiaacYcacaaIXaGaaiykaiabgEIizlaacIcacaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiaacYcacaWGIbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiaacMcacqGH9aqpcaGGOaGaamyyamaaBaaaleaacaWGUbaabeaakiabgUcaRiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGSaGaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@59B0@

we get the following table of values: (( a n , b n ))=((2,1),(3,2),(5,6),(11,30),(41,330),) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaacIcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaGaaiykaiabg2da9iaacIcacaGGOaGaaGOmaiaacYcacaaIXaGaaiykaiaacYcacaGGOaGaaG4maiaacYcacaaIYaGaaiykaiaacYcacaGGOaGaaGynaiaacYcacaaI2aGaaiykaiaacYcacaGGOaGaaGymaiaaigdacaGGSaGaaG4maiaaicdacaGGPaGaaiilaiaacIcacaaI0aGaaGymaiaacYcacaaIZaGaaG4maiaaicdacaGGPaGaaiilaiablAciljaacMcaaaa@5991@ .

From the notation we see that a recursive sequence in 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHe6aaWbaaSqabeaacaaIYaaaaaaa@3842@ could be regarded as a coupled system of two recursive sequences in MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHekaaa@3759@ . So we could as well have said: Let ( a n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3951@ and ( b n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaaaaa@3952@ be given by

a 1 2, b 1 1 a n+1 a n + b n , b n+1 a n b n . MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaikdacaGGSaGaamOyamaaBaaaleaacaaIXaaabeaakiabg2da9iaaigdacqGHNis2caWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiabg2da9iaadggadaWgaaWcbaGaamOBaaqabaGccqGHRaWkcaWGIbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaiabgUcaRiaaigdaaeqaaOGaeyypa0JaamyyamaaBaaaleaacaWGUbaabeaakiabgwSixlaadkgadaWgaaWcbaGaamOBaaqabaaaaa@54EE@

For some years the theory of chaos gained a remarkable popularity, an absolute exception for a mathematical topic. A final example in this part introduces a recursive sequence in 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHe6aaWbaaSqabeaacaaIYaaaaaaa@3842@ which is closely related with this popularity:

Example:  For a fixed pair of numbers ( c 1 , c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadogadaWgaaWcbaGaaGymaaqabaGccaGGSaGaam4yamaaBaaaleaacaaIYaaabeaakiaacMcacqGHiiIZcqWIDesOaaa@3E99@ we define the sequence (( a n , b n )) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaacIcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaGaaiykaaaa@3D6A@ recursively by

( a 1 , b 1 )( c 1 , c 2 )( a n+1 , b n+1 )( a n 2 b n 2 + c 1 ,2 a n b n + c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamOyamaaBaaaleaacaaIXaaabeaakiaacMcacqGH9aqpcaGGOaGaam4yamaaBaaaleaacaaIXaaabeaakiaacYcacaWGJbWaaSbaaSqaaiaaikdaaeqaaOGaaiykaiabgEIizlaacIcacaWGHbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiaacYcacaWGIbWaaSbaaSqaaiaad6gacqGHRaWkcaaIXaaabeaakiaacMcacqGH9aqpcaGGOaGaamyyamaaDaaaleaacaWGUbaabaGaaGOmaaaakiabgkHiTiaadkgadaqhaaWcbaGaamOBaaqaaiaaikdaaaGccqGHRaWkcaWGJbWaaSbaaSqaaiaaigdaaeqaaOGaaiilaiaaikdacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaamOyamaaBaaaleaacaWGUbaabeaakiabgUcaRiaadogadaWgaaWcbaGaaGOmaaqabaGccaGGPaaaaa@615A@
[5.2.16]

We get different value tables for different values of  ( c 1 , c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadogadaWgaaWcbaGaaGymaaqabaGccaGGSaGaam4yamaaBaaaleaacaaIYaaabeaakiaacMcaaaa@3BA5@ . The following table shows three examples with the first sequence members and their distances |( a n , b n )|= a n 2 + b n 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiiFaiaacIcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaGaaiiFaiabg2da9maakaaabaGaamyyamaaDaaaleaacaWGUbaabaGaaGOmaaaakiabgUcaRiaadkgadaqhaaWcbaGaamOBaaqaaiaaikdaaaaabeaaaaa@4598@ to the point of origin as well.

( c 1 , c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadogadaWgaaWcbaGaaGymaaqabaGccaGGSaGaam4yamaaBaaaleaacaaIYaaabeaakiaacMcaaaa@3BA5@ ( a n , b n ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadggadaWgaaWcbaGaamOBaaqabaGccaGGSaGaamOyamaaBaaaleaacaWGUbaabeaakiaacMcaaaa@3C11@ |( a n , b n )| MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiiFaiaacIcacaWGHbWaaSbaaSqaaiaad6gaaeqaaOGaaiilaiaadkgadaWgaaWcbaGaamOBaaqabaGccaGGPaGaaiiFaaaa@3E11@
(0,0) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaicdacaGGSaGaaGimaiaacMcaaaa@3966@ (0,0),(0,0),(0,0),(0,0),(0,0), MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaicdacaGGSaGaaGimaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaaGimaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaaGimaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaaGimaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaaGimaiaacMcacaGGSaGaeSOjGSeaaa@4BEC@ 0,0,0,0,0, MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiaacYcacaaIWaGaaiilaiaaicdacaGGSaGaaGimaiaacYcacaaIWaGaaiilaiablAcilbaa@3E1D@
(0,1) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaicdacaGGSaGaaGymaiaacMcaaaa@3967@ (0,1),(1,1),(0,1),(1,1),(0,1),(1,1), MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaicdacaGGSaGaaGymaiaacMcacaGGSaGaaiikaiabgkHiTiaaigdacaGGSaGaaGymaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaeyOeI0IaaGymaiaacMcacaGGSaGaaiikaiabgkHiTiaaigdacaGGSaGaaGymaiaacMcacaGGSaGaaiikaiaaicdacaGGSaGaeyOeI0IaaGymaiaacMcacaGGSaGaaiikaiabgkHiTiaaigdacaGGSaGaaGymaiaacMcacaGGSaGaeSOjGSeaaa@54C3@ 1,1.414,1,1.414,1, MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiaacYcacaaIXaGaaiOlaiaaisdacaaIXaGaaGinaiaacYcacaaIXaGaaiilaiaaigdacaGGUaGaaGinaiaaigdacaaI0aGaaiilaiaaigdacaGGSaGaeSOjGSeaaa@43F4@
(1,1) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacaGGSaGaaGymaiaacMcaaaa@3968@ (1,1),(1,3),(9,7),(32,127), MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaigdacaGGSaGaaGymaiaacMcacaGGSaGaaiikaiaaigdacaGGSaGaaG4maiaacMcacaGGSaGaaiikaiabgkHiTiaaiMdacaGGSaGaaG4naiaacMcacaGGSaGaaiikaiaaiodacaaIYaGaaiilaiaaigdacaaIYaGaaG4naiaacMcacaGGSaGaeSOjGSeaaa@4AFF@ 1.414,3.162,11.4,130.97, MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGymaiaac6cacaaI0aGaaGymaiaaisdacaGGSaGaaG4maiaac6cacaaIXaGaaGOnaiaaikdacaGGSaGaaGymaiaaigdacaGGUaGaaGinaiaacYcacaaIXaGaaG4maiaaicdacaGGUaGaaGyoaiaaiEdacaGGSaGaeSOjGSeaaa@4863@

Whereas some values of ( c 1 , c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadogadaWgaaWcbaGaaGymaaqabaGccaGGSaGaam4yamaaBaaaleaacaaIYaaabeaakiaacMcaaaa@3BA5@ produce steadily increasing distances, see e.g. the last example, there may be others where the distances are bounded. If we mark all those initial values  ( c 1 , c 2 ) MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaadogadaWgaaWcbaGaaGymaaqabaGccaGGSaGaam4yamaaBaaaleaacaaIYaaabeaakiaacMcaaaa@3BA5@ in the plane where the distances do not exceed 2 we get an extraordinary subset of 2 MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeSyhHe6aaWbaaSqabeaacaaIYaaaaaaa@3842@ , the so called Mandelbrot set. Graphical editing of its margin reveals an amazing beauty:

The (mathematical) amazement is even greater if we blow up sections of the Mandelbrot set and blow up again and again. It is rewarding to start a journey into the Mandelbrot set.

The Mandelbrot set is the most popular example of a so called  fractal. There are many more examples for fractals on the web. This site has a very exhaustive link list.

To produce fractals of your own you need information and tools.


5.1. 5.3.