Bewijs door volledige inductie

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Gebruikersavatar
Berichten: 824

Bewijs door volledige inductie

Hoi,

ik ondervind problemen met een redelijk simpel bewijs:

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

Wat ik gevonden heb:
\(\sum^n_{i=1}=\frac{1}{2}n(n+1)\)
\(\sum^{n+1}_{i=1}=\frac{1}{2}(n+1)(n+2)\)
\(\sum^n_{i=1}+n+1=\frac{1}{2}(n+1)(n+2)\)
\(\frac{1}{2}n(n+1)+n+1=\frac{1}{2}(n+1)(n+2)\)
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.

Gebruikersavatar
Berichten: 24.578

Re: Bewijs door volledige inductie

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)

Gebruikersavatar
Berichten: 824

Re: Bewijs door volledige inductie

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.

Gebruikersavatar
Berichten: 24.578

Re: Bewijs door volledige inductie

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)

Gebruikersavatar
Berichten: 824

Re: Bewijs door volledige inductie

De stelling is voldaan voor n=1:

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

Stel dat het dan geldt voor n
\(\sum^n_{i=1}=\frac{1}{2}n(n+1)\)
dan geldt het ook voor n+1
\(\sum^{n+1}_{i=1}=\frac{1}{2}(n+1)(n+2)\)
\(\sum^n_{i=1}+n+1=\frac{1}{2}(n+1)(n+2)\)
\(\frac{1}{2}n(n+1)+n+1=\frac{1}{2}(n+1)(n+2)\)
Be careful whose advice you buy, but be patient with those who supply it.

Berichten: 42

Re: Bewijs door volledige inductie

- 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 :)

Gebruikersavatar
Berichten: 24.578

Re: Bewijs door volledige inductie

Hoe kom je aan dit als eerste stap:
\(\sum^{n+1}_{i=1}=\frac{1}{2}(n+1)(n+2)\)
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)

Gebruikersavatar
Berichten: 824

Re: Bewijs door volledige inductie

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

Gebruikersavatar
Berichten: 24.578

Re: Bewijs door volledige inductie

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)

Berichten: 7.068

Re: Bewijs door volledige inductie

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:
\(\sum_{k=1}^n k = \frac{1}{2} n (n+1)\)
Eerst aantonen voor n=1:
\(\sum_{k=1}^1 k = 1 = \frac{1}{2} \cdot 1 \cdot (1+1)\)
klopt dus.

Nu veronderstellen dat de relatie klopt voor n en controleren voor n+1:
\(\sum_{k=1}^{n+1} k = (n+1) + \sum_{k=1}^{n} k = (n+1) + \frac{1}{2} n (n+1) = \frac{1}{2} 2 (n+1) + \frac{1}{2} n (n+1) = \frac{1}{2} (n+1) (n+2)\)
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.

Berichten: 42

Re: Bewijs door volledige inductie

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 ?

Gebruikersavatar
Berichten: 824

Re: Bewijs door volledige inductie

De stelling is voldaan voor n=1:

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

Stel dat het dan geldt voor n
\(\sum^n_{i=1}i=\frac{1}{2}n(n+1)\)
dan geldt het ook voor n+1
\(\sum^{n+1}_{i=1}i=\frac{1}{2}(n+1)(n+2)\)
\(\sum^n_{i=1}i+n+1=\frac{1}{2}(n+1)(n+2)\)
\(\frac{1}{2}n(n+1)+n+1=\frac{1}{2}(n+1)(n+2)\)
Ik had blijkbaar niets in mijn sommatiesymbool gezet :)
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Berichten: 24.578

Re: Bewijs door volledige inductie

mmmaster> schreef: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)

Gebruikersavatar
Berichten: 824

Re: Bewijs door volledige inductie

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.

Berichten: 42

Re: Bewijs door volledige inductie

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 ...

Reageer