Tag archieven: bewijs door inductie

Stelling van Zeckendorf

Geplaatst op door

De stelling van Zeckendorf  is vernoemd naar de Belgische dokter, legerofficier en wiskundige Edouard Zeckendorf.

De stelling zegt dat elk positief geheel getal op een unieke manier kan geschreven worden als de som van één of meer verschillende  getallen uit de rij van Fibonacci die elkaar niet opvolgen. Een dergelijke som wordt de Zeckendorfrepresentatie van een getal genoemd. De Zeckendorfrepresentatie van het getal 100 is 89+8+3.

Start met het grootste getal a_1 uit de rij van Fibonacci dat kleiner is of gelijk aan het getal n. Zoek daarna het grootste getal a_2 uit de rij van Fibonacci dat kleiner is of gelijk aan het verschil  n-a_1. Blijf dit proces herhalen totdat het verschil uiteindelijk zelf een getal is uit de rij van Fibonacci. Nu zijn a_1 en a_2 geen opeenvolgende termen van de rij van Fibonacci, want waren ze dat wel dan zou a_1+a_2 een term van de rij van Fibonacci zijn en groter zijn dan n. Dit is onmogelijk want a_1+a_2<n.

We geven ook een Python programma mee om de Zeckendorf representatie te berekenen. In het voorbeeld berekenen we deze van 2021:

Bewijs door inductie

Geplaatst op door

Vaak bestaat een probleem erin aan te tonen dat een bepaalde eigenschap geldt voor elk natuurlijk getal. Hiervoor gebruiken we het principe van de  volledige inductie 

  •  Basisstap: Men bewijst P(1)
  • Inductiehypothese: Men bewijst voor elke k dat als P(k) geldt, dan ook P(k+1) geldt.

Er bestaat ook een andere vorm, die we de sterke inductie noemen:

  • Basisstap: Men bewijst P(1) .
  • Inductiehypothese: Men bewijst voor elke k dat als P(1),P(2),\ldots,P(k) gelden, dan ook P(k+1) geldt.

Voor elk natuurlijk getal n geldt :

    \[1^2+2^2+\ldots+n^2=\frac{1}{6}n(n+1)(2n+1)\]

  • De geldigheid van de formule voor n=1 is duidelijk, want  1^2=\frac{1}{6}.1.(1+1)(2+1). Dit is de basisstap.
  • De inductiehypothese : stel dat de formule ook geldt voor n=k. Dan is: 

        \begin{align*}1^2+2^2+\ldots+k^2+(k+1)^2=&(1^2+2^2+\ldots+k^2)+(k+1)^2\\=& \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\\=&\frac{1}{6}(k+1)(2k^2+7k+6)\\=&\frac{1}{6}(k+1)(k+2)(2k+3) \end{align*}

    en dit is precies de formule voor n=k+1


					

		
		
	


				
					
	

		

						
Bewijstechnieken

			
						

				Geplaatst op   door  			

			
					


				

			
De geschiedenis van ’Bewijs dat …’ begint, net als een sprookje, vele,

vele jaren geleden met ’Er was eens…’. Er was inderdaad eens een tijd

waarin geen bewijzen bestonden nl, tijdens de Babylonische periode,

want in de Babylonische wiskunde – 4000 jaar geleden – was er geen

spoor te vinden van het begrip bewijs, noch van enige deductieve redenering.

Babylonische wiskunde, zoals ook deze tijdens de Egyptische farao’s,

bestond uit recepten om een concreet probleem met concrete gegevens

op te lossen. Het was een wiskunde zonder bewijzen, zonder verklaringen!

Toch bleek na verloop van tijd ergens de noodzaak voor meer

structuur omdat elk gelijkaardig probleem telkens moest worden hernomen

volgens het gegeven recept.


Lees hier over de verschillende bewijstechnieken.

bewijzen