WisFaq!

Bewijs met volledige inductie

Ik heb een vraag:
Ik moet bewijzen dat voor elke n4 geldt n!2^n.

Nu weet ik precies hoe het ongeveer gaat maar weet op een gegeven moment niet hoe ik het moet opschrijven.
Mijn bewijs gaat als volgt; ik zal aantonen waar ik problemen heb:

1) Klopt voor n4 want 4·3·2·1=24 2⁴=16
2) Inductieveronderstelling: Klopt voor n!2^n

Bewijs: (n+1)!=(n+1)·n! 2^(n+1)=2^n·2^1=(2^n)·2
Nu zit ik vast:
Ik begrijp dat aan de hand van mijn inductieveronderstelling ik kan gebruiken dat n! 2^n en dat ik dus moet laten zien dat (n+1)2.
Dit is zo want n4 maar ik weet niet zeker of ik dit uberhaupt zo mag aantonen en of ik het zo mag opschrijven:

(n+1)n! 2·(2^n)
(n+1) 2

Ik heb kortom met de meeste bewijzen die ik moet doen het probleem wanneer ik klaar ben en/of hoe ik het moet opschrijven. Graag wat feedback.

Alvast bedankt.

Melchior
28-11-2005

Antwoord

Beste Melchior,

Het ziet er allemaal goed uit, we moeten dus aantonen dat (n+1)n! 2.2ⁿ.

We hebben dus iets van de vorm ab cd en indien a, b, c en d positief zijn geldt dit sowieso indien a c en b d. De inductiehypothese veronderstelt dat één van deze ongelijkheden klopt.
De tweede volgt dan triviaal zoals je zelf al aangaf. We willen immers dat n+1 2, maar dat geldt steeds voor (los op naar n) n 1, maar we zitten in het geval n 4 dus...

mvg,
Tom

td
28-11-2005