Volledige inductie

Henkie · Bericht door **Henkie** » 08 sep 2013, 20:47

Beste forumleden,

Ik moet via volledige inductie bewijzen dat

$n < 2^n$

door n = 1 in te vullen krijg ik:

$1 < 2^1$ , wat klopt.

Vervolgens neem ik aan dat $N < 2^N$ ook klopt.

Dan vul ik voor $n = N+1$

$(N+1) < 2^{N+1}$

ik herschrijf dit naar $(N+1)<2*2^N$ $=\frac{N+1}{2}<2^N$

En na dit ingevuld te hebben zou ik niet weten hoe ik het bewijs af moet maken, dus misschien dat iemand het mij uit zou kunnen leggen?

Alvast bedankt

Bericht door **arie** » 08 sep 2013, 21:06

Je bent er bijna, je moet alleen nog aantonen dat

$\frac{N+1}{2} \;<\; 2^N$

Je weet (inductiehypothese) dat

$N \;<\; 2^N$

Kan je verder ook aantonen dat

$\frac{N+1}{2} \; \leq \; N$

voor N > 1 ?

NOOT: als dat lukt heb je immers aangetoond dat

$\frac{N+1}{2} \;\leq\; N \;<\; 2^N$

en dus ook dat

$\frac{N+1}{2} \;<\; 2^N$

Bericht door **op=op** » 09 sep 2013, 08:01

Systematisch:
Je weet $N < 2^N$

Je wilt aantonen $N+1 < 2^{N+1}$

Nu is
$N+1 <$ (volledige inductie) $2^N+1$

Rest nog om aan te tonen dat
$2^N+1 < 2^{N+1}$

Henkie · Bericht door **Henkie** » 09 sep 2013, 17:53

Allereerst bedankt voor de snelle reacties.

Vanaf de stap $\frac{N+1}{2} < 2^N$

heb ik $\frac{N+1}{2} \leq N$ gemaakt.

Dit heb ik omgeschreven tot $N \leq 2N-1$

Hier heb ik volgens mij bewezen dat P(N+1) klopt, omdat $N\epsilon \mathbb{N}$ .

Echter vind ik de stap van $\frac{N+1}{2}<2^N$ naar $\frac{N+1}{2}\leq N$ een lastige stap, vanwege $<$ naar $\leq$ .

Heeft iemand tips hoe ik deze stap makkelijk kan onthouden?

Alvast bedankt.

Bericht door **SafeX** » 09 sep 2013, 18:21

Kan je 'de weg' van op=op niet volgen ...

Wiskundeforum

Volledige inductie

Volledige inductie

Re: Volledige inductie

Re: Volledige inductie

Re: Volledige inductie

Re: Volledige inductie