bewijs met volledige inductie

[MathBoy]

Ik probeer onderstaand gegeven te bewijzen met volledige inductie, maar ik weet niet of dit helemaal klopt aangezien dit nog maar mijn eerste bewijs is met volledige inductie. Zouden jullie me willen vertellen of er fouten in ziiten?
 
Dit is het gegeven:

Opgave - NWO 2009 vraag 5

Honderd blanco kaarten worden genummerd: een kaart met op beide zijden het getal 1, een kaart met op beide zijden het getal 2, enzovoorts, tot en met een kaart met op beide zijden het getal 100. De kaarten worden geordend op een stapel gelegd, de kaart met het getal 1 boven. De volgorde van de kaarten wordt telkens per stap als volgt veranderd: bij de 1e stap wordt de bovenste kaart omgedraaid en terug op de stapel gelegd (er verandert hierdoor natuurlijk niets), bij de 2e stap worden de bovenste 2 kaarten gepakt, omgedraaid en terug op de stapel gelegd, ..., bij de ie stap worden de bovenste i kaarten gepakt, als stapeltje op hun kop gelegd en terug op de stapel gelegd, ..., bij de 100e stap worden alle 100 kaarten gepakt en als stapel op hun kop gelegd. Bij de 101e stap wordt weer alleen de bovenste kaart omgedraaid, bij de 102e stap de bovenste 2, enzovoorts.

Bewijs dat als we zo doorgaan, de kaarten na een aantal stappen weer op hun uitgangsposities terug zijn.
Dan nu mijn bewijs:
 
We bekijken deze situatie eerst eens met minder kaarten.
Bij 1 kaart zou de uitgangspositie al bereikt worden na 1 stap.
Bij 2 kaarten al na 4 stappen.
Bij 3 kaarten al na 9 stappen.
Enz...
Ik vermoed nu dus dat je n-aantal kaarten terug in een uitgangspositie kan verkrijgen na n²stappen.
Dit ga ik bewijzen a.d.h.v volledie inductie.
Wanneer we n=0 nemen dan zien we dat de uitgangspositie bereikt wordt na 0²= 0 stappen.
Nu hoeven we enkel nog te kijken of de uitspraak ook geldt voor n+1:
Wanneer we n=1 nemen dan wordt de uitgangspositie bereikt na 1 stap en 1 = 1² dus de eigenschap geldt nu dus ook voor n+1.
We hebben nu dus bewezen dat de eigenschap geldt voor alle n element van N, dus ook voor n=100 die zijn uitgangspositie zal bereiken na 10.000 stappen.
 
Alvast bedankt voor de hulp!
 

[Safe]

Je hebt nu alleen n=1 bewezen en dat is niet voldoende. Uitgaande van: de bewering geldt voor n=k, te bewijzen dat de bewering geldt voor n=k+1.

[MathBoy]

Ik had als k=0 en k+1=1. Mag dit dan niet?

[Safe]

Nogmaals, je stelt vast dat de bewering geldt voor n=1. En dat is natuurlijk niet voldoende.

[mathfreak]

Als P(n) een uitspraak over een natuurlijk getal n is die je met volledige inductie wilt bewijzen doe je het volgende: je toont eerst aan dat P(0) geldt. Vervolgens veronderstel je dat voor een gegeven natuurlijk getal k P(k) geldt (dit heet de inductiehypothese) en uitgaande van de geldigheid van P(k) bewijs je de geldigheid van P(k+1). De stap waarbij je uitgaande van de geldigheid van P(k) de geldigheid van P(k+1) bewijst heet de inductiestap. Omdat P(0) geldt en omdat uit de geldigheid van P(k) de geldigheid van P(k+1) volgt, is daarnee de geldigheid van P(n) voor alle natuurlijke getallen n bewezen. Neem dus aan dat de uitspraak die je wilt bewijzen juist is voor een gegeven natuurlijk getal k en toon aan de hand daarvan aan dat de uitspraak ook juist is voor k+1.

[MathBoy]

Klopt dit aangepaste bewijs dan nu?
 
We bekijken deze situatie eerst eens met minder kaarten.
Bij 1 kaart zou de uitgangspositie al bereikt worden na 1 stap.
Bij 2 kaarten al na 4 stappen.
Bij 3 kaarten al na 9 stappen.
Enz...
Ik vermoed nu dus volgende eigenschap: n kaarten verkrijgen hun uitgangspositie na n² stappen.
Dit ga ik bewijzen a.d.h.v volledige inductie.
P(0)=0.
We nemen nu P(1) (k=1). We zien dat de uitgangspositie na 1 keer omdraaien wordt bereikt. Aangezien 1=1²klopt de eigenschap dus  voor k=1. 1 behoort dus al tot de verzameling V waarvoor deze eigenschap geldt.
Als de eigenschap geldt voor , dan gaan we kijken of de eigenschap ook klopt voor P(k+1). Na 1 stap verkrijg je (van boven naar beneden) 1-2, na 2 stappen 2-1, na 3 stappen 2-1 en na de 4de stap de uitgangspositie, namelijk 1-2. Aangezien 4=2², klopt de eigenschap dus ook voor P(k+1). 2 behoort dus ook tot de verzameling V.
V=(1,2,3,4,...)
P(100) behoort ook tot V. We weten nu dus dat de 100 kaarten na 100²=10.000 stappen terug hun uitgangspositie zullen bereiken.

[EvilBro]

Je hebt niet helemaal juist hoe volledige inductie werkt. Een bewijs met volledige inductie bestaat uit 2 stappen. De eerste stap is dat je bewijst dat hetgeen je wilt bewijzen voor een specifieke waarde geldt. De tweede stap is dat je bewijst dat als je aanneemt dat het gestelde geldt voor een niet nader gespecificeerde waarde k, dat dit ook geldt voor (k + 1). Bij de tweede stap is het belangrijk dat je je realiseert dat het niet voldoende is om een voorbeeld te vinden dat toevallig voldoet (dit doe je nu wel). Je moet de algemene relatie aantonen: als het geldt voor k dan moet het ook gelden voor (k+1).
 
Los hiervan:  Bekijk de situatie met 4 kaarten.
[1,2,3,4]
[1,2,3,4]
[2,1,3,4]
[3,1,2,4]
[4,2,1,3]
[4,2,1,3]
[2,4,1,3]
[1,4,2,3]
[3,2,4,1]
[3,2,4,1]
[2,3,4,1]
[4,3,2,1]
[1,2,3,4]
Dat zijn geen 16 stappen...

[MathBoy]

Oké ik begrijp het nu denk ik. Ik zal naar een andere manier op zoek moeten gaan om het bovenstaande te bewijzen.
Bedankt voor jullie hulp allemaal!

[EvilBro]

Stel je hebt een stapel van n kaarten. Deze stapel kan in n! unieke volgordes liggen.
Stel je hebt een algoritme dat de volgorde van een stapel kaarten op een vaste manier verandert (bijvoorbeeld: de eerste kaart gaat naar de derde positie, de tweede kaart gaat naar de tweede positie, enz.). Door dit algoritme op een volgorde toe te passen, krijg je een nieuwe volgorde. Deze nieuwe volgorde kan hetzelfde zijn als de volgorde die je in het algoritme stopte.
Stel dat je dit algoritme n! keer achter elkaar toepast. Je genereert dan n! volgordes (bij elke stap een volgorde). Samen met de beginvolgorde maakt dit (n!+1) volgordes. Er zijn maar n! unieke volgordes, dus ten minste 1 van deze n!+1 volgordes zal niet uniek zijn.
Stel dat de k-de en de n-de volgorde niet uniek zijn. Dit wil zeggen dat als je het algoritme (n-k) keer toepast, beginnende met de k-de volgorde dat je dan de n-de volgorde krijgt. Het algoritme doet echter niets met de waarden van kaarten, enkel iets met de posities. Het algoritme (n-k) keer toepassen levert dus geen verplaatsing van de kaarten op. Als je het algoritme (n-k) keer toepast op de beginpositie dan heb je dus weer de beginpositie.

Stel je hebt een stapel van n kaarten. Op deze stapel doe je een volledige cyclus van je algoritme (dus eerst 1 kaart omdraaien, dan twee, t/m n kaarten). Dit levert je een beschrijving op van naar welke positie elke kaart zal bewegen na een volledige cyclus. Een volledige cyclus is dus een algoritme dat de volgorde van een stapel kaarten op een vaste manier verandert. Alles dat hierboven gezegd is, zal dus gelden. Tevens zal dit alles gelden in het specifieke geval van n=100. Daarmee is dus bewezen dat de uitgangspositie weer een keer langs zal komen.