Tag archieven: bijlessen wiskunde

Recursie

Geplaatst op door

Een rij van getallen kan je geven met behulp van een recursief  voorschrift zoals bijvoorbeeld : a_1=1 en a_n= 2a_{n-1}+1. Soms kan je uit dit recursief voorschrift een expliciete formule afleiden voor de algemene term van de rij. Soms kan dat niet, maar is het mogelijk, via recursie, de parameters te herleiden tot waarden waarvoor je het probleem wel kan oplossen.

Een eerlijk muntstuk wordt n keer opgeworpen. Wat is de kans op twee opeenvolgende keren kop ergens in de rij worpen?

  • Noteer met P_n de kans dat er nergens twee keer kop na elkaar voorkomt is de rij van n worpen.
  • Het is duidelijk dat P_1=1 en P_2=\frac{3}{4}.
  • Stel n>2. Dan zijn er twee mogelijkheden naargelang de eerste worp kop of munt is.
  • Als je eerst munt gooit, dan is de kans dat je nergens twee keer kop na elkaar hebt in de volgende n-1 worpen gelijk aan P_{n-1}.
  • Gooi je eerst kop, dan moet de tweede worp munt zijn, want anders zou je twee keer kop na elkaar hebben. De kans dat je nergens twee keer kop na elkaar hebt in de volgende n-2 worpen gelijk aan P_{n-2}.
  • Uit de vorige twee punten vinden we tenslotte dat

        \[P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\]

  • Dit kan je herleiden tot 2^nP_n=2^{n-1}}P_{n-1}+2^{n-2}P_{n-2}. Of via S_n=2^nP_n:

        \[S_n=S_{n-1}+S_{n-2}\]

  • Dit is de rij van Fibonacci, waarbij S_n het n+2 de getal in de rij van Fibonacci is. Dus S_n=F_{n+2}. De gezochte kans op twee opeenvolgende keren kop ergens in de rij van n worpen, met n>2 is dan X=1-P_n=1-\frac{F_{n+2}}{2^n}.

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


					

		
		
	


				
					
	

		

						
De vergelijking van Pell

			
						

				Geplaatst op   door  			

			
					


				

			
Begin 17de eeuw. Door de Renaissance was de belangstelling voor de Griekse en Alexandrijnse cultuur weer opgewekt. Ook de werken van de oude wiskundigen werden herontdekt en heruitgegeven. Zo gaf Bachet (1557-1638) de werken van Diophantus in het Grieks en het Latijn uit. Pierre de Fermat (1601-1665) bestudeerde dat boek en loste vele problemen eruit op. In februari 1657 schreef Fermat een brief naar zijn landgenoot Frenicle (1602-1675) waarin hij vroeg om de diophantische vergelijkingen x^2-61y^2=1 en x^2-109y^2=1 op te lossen.


Frenicle deed meer: hij slaagde erin de vergelijking x^2-Ay^2=1 op te lossen voor alle niet-kwadratische waarden van A \leq 150. Beide Fransen voerden een drukke correspondentie met de Engelse wiskundigen Wallis (1616-1703) en diens medewerker Lord Brouncker (1620-1684). Voor de sport aanvaardden ze de uitdaging om de vergelijkingen x^2-151y^2=1 en x^2-313y^2=1  proberen op te lossen. Wallis en Brouncker probeerden te bewijzen dat de vergelijking x^2-Ay^2=1 ,  voor  niet-kwadratische waarden van A, altijd oplossingen heeft. Hieronder een afbeelding van John Wallis en Lord Brouncker






 


 


 


 


 


 


 


Pell (1611-1685) heeft een uitgave en vertaling van een boek waarin de oplossing hiervan staat, verzorgd, en Euler (1707-1783) heeft hem, per vergissing, ten onrechte de verdienste van de oplossing toegekend en tevens Pells nam verbonden aan die vergelijkingen, zoals blijkt uit een brief aan Lagrange (1736-1813). Lagrange was niet tevreden met het bewijs van de oplosbaarheid, zoals dat gegeven werd door Wallis. In 1768 slaagde hij erin een sluitend bewijs te vinden.


Het vinden van een oplossing is echter zeer lastig. Voor de diophantische vergelijking x^2-Ay^2=-1 is er zelfs niet altijd een oplossing.

					

		
		
	


				
					
	

		

						
Contradictie

			
						

				Geplaatst op   door  			

			
					


				

			
Redeneren door  tegenspraak gaat uit van de veronderstelling dat de conclusie niet juist is en probeert door argumenteren te komen tot iets wat in tegenspraak is met gegeven is (de indirecte methode) of iets wat in tegenspraak is met iets waarvan we weten dat het waar is (reductio ad absurdum).




Bewijs dat de onderstaande reeks divergeert  


      \[1+\frac{1}{2}+\frac{1}{3}+\cdots\]




    

  •  We veronderstellen dat de reeks niet divergeert maar dus convergeert naar de waarde r.
    • 

  •  Dus r=(1+\frac{1}{2})+(\frac{1}{3}+ \frac{1}{4})+(\frac{1}{5}+ \frac{1}{6})+\cdots.
    • 

  •  De eerste term van elk groepje van twee termen is groter dan de tweede, dus kunnen we schrijven dat

          \[r> (\frac{1}{2}+ \frac{1}{2})+ (\frac{1}{4}+ \frac{1}{4})+ (\frac{1}{6}+ \frac{1}{6})+\cdots = 1+\frac{1}{2}+ \frac{1}{3}+\cdots=r\]
    

    .
    • 

  • Dus is r>r en dat is onmogelijk. Bijgevolg is de harmonische reeks niet convergent, maar wel divergent.
    •