WisFaq!

Volledige inductie bij een ongelijkheid

Te bewijzen met het principe van volledige inductie dat 'n$\in$$\mathbf{N}$ geldt dat:

n²$\leq$2ⁿ+1

Voor n=0 geldt:

0²$\leq$2⁰+1
0$\leq$2
Dit is geldig.

Stel dat de stelling klopt voor alle natuurlijke getallen n, dan zou de stelling volgens het principe van volledige inductie ook moeten kloppen voor elke opvolger n+1.

(n+1)²$\leq$2ⁿ⁺¹+1

Met wat probeersels heb ik uiteindelijk besloten dit te schrijven als:

2ⁿ⁺¹+1$\geq$(n+1)²
2·2ⁿ$\geq$n²+2n
2ⁿ$\geq$¹/₂n²+n

Is dit nuttig geweest? Het omwisselen van de leden? Dat is mijn eerste vraag. Het leek voor mijn bewijs wel nuttig, maar ik liep ook hier vast dus misschien maakt het wel helemaal geen verschil of ik dit wel of niet doe. Hoe ik vast loop wordt zo duidelijk.

Per inductie geldt dat:

n²$\leq$2ⁿ+1
2ⁿ$\geq$n²-1

Aan te tonen is dus dat geldt dat:
2ⁿ$\geq$¹/₂n²+n
Terwijl je al weet dat geldt dat:
2ⁿ$\geq$n²-1

Het zijn geen vergelijkingen natuurlijk, dus kan ik niet simpelweg een vervanging toepassen. Ik heb wel iets bedacht wat me mogelijk leek, maar ik ben er niet uitgekomen. Mijn idee was dat je al weet dat 2ⁿgroter is dan een bekende waarde, en als je aan moet tonen dat 2ⁿ groter is dan een ander getal, dan moet je aantonen dat dat andere getal dezelfde waarde of een grotere waarde heeft dan die waarde waarvan al bekend is dat 2ⁿ groter is. Vervolgens dacht ik juist dat aan te tonen is dat dat andere getal dezelfde waarde of een kleinere waarde heeft dan die waarde waarvan al bekend is dat 2ⁿ groter is. Ik vind het nogal verwarrend.
Ik zou het fijn vinden als mijn eventuele denkfout hier zou worden kunnen uitgelegd: welke van de twee manieren is goed en waarom? Of zijn ze allebei fout, waarom?

Ik denk dat ik het nog lastig vindt om te werken met ongelijkheden omdat daar nooit echt veel aandacht aan is besteed.

Hoe kan ik hier verder . Ik hoop dat de beantwoorder gericht antwoord kan geven op al mijn vragen die ik heb gesteld in deze vraag. Ik denk dat mijn beeld fout is en ik geloof dat het antwoord op deze vraag wel eens heel leerzaam zou kunnen zijn.

Hartstikke bedankt!

Bart Kleijngeld
21-9-2006

Antwoord

Dag Bart,

Je basisstap is natuurlijk juist, en ook bij de inductiestap zit je op de goede weg. Dus laten we vertrekken van de stand van zaken zoals je die zelf gaf:

'Aan te tonen is dus dat geldt dat:
2ⁿ$\geq$1/2n²+n
Terwijl je al weet dat geldt dat:
2ⁿ$\geq$n²-1'

In de alinea die daarop volgde was de eerste helft fout, de tweede juist. Kijk, als je weet dat A$\geq$B, en je kan ook nog aantonen dat B$\geq$C, dan heb je A$\geq$B$\geq$C dus A$\geq$C. Echter niet omgekeerd: als A$\geq$B en A$\geq$C dan volgt daaruit niet noodzakelijk dat B$\geq$C.

In dit geval heb je A=2ⁿ, B=n²-1, C=n²/2+n. Dus als je kan bewijzen dat B$\geq$C ben je er. Die ongelijkheid komt neer op n²-2n-2$\geq$0. Dan moet je nog nagaan of die ongelijkheid geldt voor alle n. Dat kan op meer manieren, bijvoorbeeld zo:

Het linkergedeelte is de grafiek van een dalparabool, dus de ongelijkheid zal geldig zijn zolang n niet tussen de twee nulpunten van n²-2n-2 ligt. Bereken deze twee nulpunten en besluit dat de ongelijkheid geldig is voor n$\geq$3.

Of zo:
n²-2n-2$\geq$0 $\Leftrightarrow$ (n-1)²$\geq$3 waaruit je ook weer haalt dat n minstens 3 moet zijn.

Of nog, met dank aan kn:
(n+1)²=n²+2n+1$\Leftarrow$2n²+1$\Leftarrow$2ⁿ⁺¹+1 want
n²+2n-2n²=2n-n²=n(2-n)$\Leftarrow$0 voor n=2,3,..

Conclusie: als je de opgave op deze manier wil oplossen, moet je de basisstap nagaan voor n=0,1,2,3. Voor n minstens 3 kan je dan de inductiestap toepassen.

Een andere methode, zonder inductie, gebruikt het binomium van Newton: bekijk 2ⁿ als (1+1)ⁿ, volgens het binomium is dat gelijk aan $\sum$C(n,k)·1^k·1^n-k=C(n,0)+C(n,1)+...+C(n,n). Dit is gelijk aan 1 + n + (n²-n)/2 + ... + (n²-n)/2 + n + 1 = n²+n+2+... dus zeker groter dan n²-1. Deze redenering gaat natuurlijk alleen op als n groter is dan 4, want anders vallen er termen samen. Dus ook met deze methode moet je nog een aantal gevallen (n=0,1,2,3,4) afzonderlijk nagaan.

Nog een andere manier maakt gebruik van de afgeleide... Dus methodes genoeg :-)

Groeten,
Christophe.

Christophe
21-9-2006