WisFaq!

Een bewijs met inductie?

Ik moet het volgende bewijzen en ik vraag me af of ik hier ook hierop ook bewijs met volledige inductie kan toepassen? Zo ja, hoe dan?

Bewijs dat: de som van "n boven k" vanaf k = 0 tot en met n, is gelijk aan 2ⁿ
voor nÎ0

Alvast bedankt!

Selma
25-9-2007

Antwoord

Beste Selma,

Ja, dat is zelfs een heel mooi voorbeeld voor volledige inductie.
Je wil bewijzen:

Het gaat dus om de het totaal aantal combinaties ter grootte 0 t/m n, die je kan kiezen uit n elementen.
Stel dat aantal = a.
Voeg nu een nieuw element toe, zodat je n+1 elementen hebt.
Nu kan je weer dezelfde a combinaties maken als daarnet, met n elementen, maar je kan ook aan elke combinatie dat nieuwe element toevoegen. Daardoor heb je twee keer zoveel combinaties, dus 2×a.
Hiermee is bewezen dat als je voor n=p in totaal 2^p combinaties hebt, dan zijn er voor n=p+1 in totaal 2×2^p=2^p+1 combinaties mogelijk.

Nu nog de inductievoorwaarde: De formule geldt voor n=1. (Laat dat zien).

Een andere manier is door te denken aan de driehoek van Pascal.
Daarin is de gevraagde som de som van de getallen in de n^e rij.
Elk element in rij p wordt toegevoegd aan twee elementen in rij p+1, zodat het totaal in die rij twee keer zo groot is als in rij p.

Misschien nog eenvoudiger: In een roosterdiagram zet je op alle roosterpunten het aantal kortste routes naar dat punt vanaf de oorsprong. Dat zijn de binomiaalcoeefficienten.
Op diagonaal p vindt je dan alle termen van jouw som als n=p.Vanuit elk punt op diagonaal p kan je op 2 manieren naar diagonaal p+1 toe, dus daar is het totaal ook twee keer zo groot.

Zie ook: Driehoek van Pascal

Daar wordt eerst het binomium van Newton bewezen en vervolgens:
(1+1)ⁿ=jouw som. Kijk maar eens.

Was dat de bedoeling?

ldr
25-9-2007