Springen naar inhoud

Bewijs door volledige inductie


  • Log in om te kunnen reageren

#1

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:23

Hoi,

ik ondervind problemen met een redelijk simpel bewijs:

1+2+3+...+(n-1)+n=(1/2)n(n+1)

Wat ik gevonden heb:

LaTeX
LaTeX
LaTeX
LaTeX

Als ik nu verder uitwerk komt het niet gelijk uit... Wat doe ik mis?
Be careful whose advice you buy, but be patient with those who supply it.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:28

Na controle voor (bijvoorbeeld) n = 1, veronderstel je voldaan voor n = k: 1+2+...+k = k(k+1)/2.

Geldt dan ook: 1+2+...+k+(k+1)? Dit is, onder de hypothese, gelijk aan het volgende:

(1+2+...+k)+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)/2, qed.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#3

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:37

Dus zit het al in de tweede stap fout bij mij?
Be careful whose advice you buy, but be patient with those who supply it.

#4

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:40

Ik zie niet goed wat je doet... Je schrijft daar drie sommaties, maar wat is je inductiehypothese, waar ga je verder, wat wil je bewijzen?

Volledige inductie =
- controleer voor kleinste n
- veronderstel voldaan voor n = k
- uitgaande van die veronderstelling, toon geldigheid aan voor n = k+1.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#5

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:44

De stelling is voldaan voor n=1:

1=(1/2)*1*(1+1)

Stel dat het dan geldt voor n

LaTeX

dan geldt het ook voor n+1

LaTeX
LaTeX
LaTeX
Be careful whose advice you buy, but be patient with those who supply it.

#6

mmmaster>

    mmmaster>


  • >25 berichten
  • 42 berichten
  • Gebruiker

Geplaatst op 04 oktober 2006 - 20:45

- controleer voor kleinste n


Een n-waarde is voldoende , moet niet de kleinste zijn :)


Kortom je ondersteld het voor k , schrijf dit op...

Dan neem je het voor k+1 , je probeert wat apart te zetten zodat je die formule voor k erin krijg , deze heb je ondersteld als gekend en vervang je dus. Dan werk je verder uit en bekom je dat dit ook geldt voor k+1.

Nu mogen we beschouwen dat dit voor een willekeurige k geldt :)

Dit is het principe van volledige inductie :)

#7

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:46

Hoe kom je aan dit als eerste stap:

LaTeX

Of is dat wat je wil bereiken/bewijzen (dat is niet duidelijk!).
Het enige dat je op dit moment 'weet' is dat 1+...+k = k(k+1)/2.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#8

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:46

mmmaster, heb je mijn post hierboven al gelezen?
Be careful whose advice you buy, but be patient with those who supply it.

#9

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:47

Een n-waarde is voldoende , moet niet de kleinste zijn :)

Niet noodzakelijk, maar dat is wel handig: als je voor een niet minimale n controleert, dan weet je nog niet of het geldt voor de waarden kleiner dan die n. Beginnend bij de kleinst mogelijk n levert het bewijs voor alle mogelijke n, dat lijkt me toch handig :)
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#10

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:48

Volledige inductie werkt simpel gezegd in twee stappen. Eerst toon je aan dat de relatie geldt voor een bepaalde waarde n. Daarna toon je aan dat als de relatie geldt voor een willekeurige waarde n, hij ook geldt voor n+1. Daarmee bewijs je dus dat de relatie geldt van je eerder gecontroleerde waarde n en hoger.

In dit geval is de relatie die je wilt controleren:
LaTeX

Eerst aantonen voor n=1:
LaTeX
klopt dus.

Nu veronderstellen dat de relatie klopt voor n en controleren voor n+1:
LaTeX

Je hebt nu dus bewezen dat de relatie geldt voor een bepaalde n en alle daarop opvolgende waarden voor n. Hiermee is je bewijs klaar.

#11

mmmaster>

    mmmaster>


  • >25 berichten
  • 42 berichten
  • Gebruiker

Geplaatst op 04 oktober 2006 - 20:49

Hum hum hum,ik dacht mij te herinneren dat uit het bewijs van volledige inductie volgde dat het geldt voor ALLE n-waarden en dat daar geen extra voorwaarde aan opgelegd werd... dus heeft dat niets te maken met die inductiehypothese.

Niet ?

#12

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:49

De stelling is voldaan voor n=1:

1=(1/2)*1*(1+1)

Stel dat het dan geldt voor n

LaTeX

dan geldt het ook voor n+1

LaTeX
LaTeX
LaTeX


Ik had blijkbaar niets in mijn sommatiesymbool gezet :)
Be careful whose advice you buy, but be patient with those who supply it.

#13

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 04 oktober 2006 - 20:52

Hum hum hum,ik dacht mij te herinneren dat uit het bewijs van volledige inductie volgde dat het geldt voor ALLE n-waarden en dat daar geen extra voorwaarde aan opgelegd werd... dus heeft dat niets te maken met die inductiehypothese.

Niet ?

Bedoel je nu onafhankelijk van de "startwaarde"? Dat lijkt me sterk... Het principe steunt net op "als je weet voor k, dan ook voor de volgende". Maar: je weet het slechts voor de gecontroleerde k (waarvan ik zei dat je best/doorgaans de kleinst mogelijke waarde neemt), niet voor lagere k.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#14

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 04 oktober 2006 - 20:57

Ik zag nu pas EvilBro zijn post.

Als ik het goed begrijp, mag ik dus stoppen met mijn bewijs bij mijn tweede stap?
Be careful whose advice you buy, but be patient with those who supply it.

#15

mmmaster>

    mmmaster>


  • >25 berichten
  • 42 berichten
  • Gebruiker

Geplaatst op 04 oktober 2006 - 20:58

Ik moet eerlijk zijn, ik heb dit altijd zo ingedachte gehad en heb dit nergens tegen gekomen dat dit niet zo was in een les / oefening. Kzou eens moeten navragen...

Maar nu ik erover nadenk...

Het lijkt me logisch dat je iets kan vinden dat het geldt vanaf 1 ... (bewijs via volledige inductie) , maar het niet geldt voor 0 , maar dan begint die eindeloze discussie over de natuurlijke getallen weer :)

kzou het nu graag ook wel eens weten ...





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures