Matematisk induksjon

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gjest

Noen som kan hjelpe meg med denne oppgaven?

Bevis ved matematisk induksjon at
6n – 1
er delelig med 5 for alle naturlige tall n.


Har begynt litt, men vet ikke om det blir riktig og videre står jeg helt fast.

• Påstanden som skal bevises er: (6n – 1) / 5
• For å vise basissteget, at P(0) er sann, erstatter jeg n med 0 og får følgende påstand:
P(0) = (60 – 1) / 5
= (1 – 1) / 5
= 0
• Ved å regne ut venstre- og høyresiden, får jeg 0 på hver side og ser at påstanden er sann for tallet 0.
• Nå skal jeg vise induksjonssteget, at hvis P(n) er sann, så er P(n + 1) sant for alle naturlige tall n.
Gjest

Et spørsmål til: Hvorfor kan vi ikke bruke matematisk induksjon til å bevise påstander om brøktall eller reelle tall, på samme måte som vi gjør for naturlige tall?

Håper noen kan hjelpe :D
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Du må ha skrevet ned påstanden din feil. For $n=2$ er $6\cdot 2 - 1 = 11$, men $11$ er et primtall og er dermed definitivt ikke delelig på $5$. Basissteget du prøver å vise er også umulig. Mente du kanskje heller å skrive at $5$ deler $6^n-1$?

Over til ditt andre spørsmål: Det viser seg (etter litt googling) at det er en måte å indusere over $\mathbb{R}$, men den kan nødvendigvis ikke være helt lik til matematisk induksjon over $\mathbb{N}$ (som jeg prøver å gi en liten pekepinn på under). Jeg besitter definitivt ikke kunnskapen til å si noe mer om det, men håper noen andre mer erfarne på forumet kan utdype!

Svarer på ditt spørsmål om hvorfor induksjon (på naturlige tall) fungerer først: La $P(n)$ være en påstand om et gitt tall. Med helt vanlig matematisk induksjon prøver vi å vise et grunntilfelle, og at dersom $P(n)$ er sann, så er $P(n+1)$ også sann. Du kan tenke på dette som dominobrikker som faller. La oss først anta at vi klarer å vise grunntilfellet, f.eks $n=1$. Altså er $P(1)$ sann. Dersom vi klarer å vise at $$P(n) \text{ er sann} \implies P(n+1) \text{ er sann}$$ så vil vi sette i gang en kjedereaksjon. Hvorfor det? Jo fordi hvis $P(1)$ er sann så sier implikasjonen oss at $P(1+1)=P(2)$ også er sann, men nå sier implikasjonen på nytt igjen at siden $P(2)$ er sann, så er $P(2+1)=P(3)$ sann. Denne prosessen fortsetter i det uendelige.

Et fundamentalt problem som presenterer seg selv med en gang er at den samme formuleringen ikke helt funker med reelle tall. For $\mathbb{N}$ er tallene "så ordnet" at det er lett å jobbe seg oppover dem induktivt. Hvis vi klarer å vise basistilfellet og at $P(n) \text{ sann} \implies P(n+1) \text{ sann}$, så jobber vi oss oppover i $\mathbb{N}$ uten å "glemme" noen tall på veien. For $\mathbb{R}$ er det derimot ikke en slik ordning, og det blir på en måte hovedproblemet i hvorfor man ikke kan gjøre induksjonen på samme måte over $\mathbb{R}$. La oss si at (dette trenger nødvendigvis ikke å være sant) det hadde vært mulig å vise at $P(x) \text{ sann } \implies P(x+h) \text{ sann }$ for en "steglengde" h. La oss så si at vi hadde klart å vise et basistilfelle $P(1)$. Hvordan skulle vi da valgt steglengden $h$ slik at vi "treffer" alle tallene mellom 1 og 2? Hvis du tenker litt over det så finner du at det ikke er mulig; uansett hvor liten du velger $h$ kan du alltid finne en mindre $h$. Dette viser at induksjonen ikke kan fungere helt på samme måte som i tilfellet med de naturlige tallene.

I beviset av at induksjon fungerer, bruker man et aksiom kalt velordningsprinsippet. Det sier at enhver ikke-tom mengde $\mathcal{S}$ av ikke-negative heltall inneholder et minste element. Her er det snakk om mengder med heltall, så vi kan ikke ta i bruk det samme aksiomet hvis vi eventuelt skulle bevist en lik versjon av induksjon over $\mathbb{R}$.
Gjest

Tusen takk for svar!
Oida! Det skulle stå 6^n - 1. Den opphøyde n forsvant visst da jeg limte inn teksten... Da skjønner jeg at det var litt vanskelig å løse den :)
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Induksjonssteget blir $6^{n+1}-1 = 6^n \cdot 6 - 1 = \overbrace{(5m + 1)}^{\text{av induksjonshypotesen}} \cdot 6 - 1 = 6 \cdot 5m + 5 = 5(6m + 1)$ der $m \in \mathbb Z$ og siste del er klart delelig på 5.
Bilde
Gjest

Tusen hjertelig takk for svar! Det hjelper masse! Hvordan kom du frem til at induksjonshypotesen er 5m + 1?
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Hypotesen er at $6^n - 1 = 5m$ for et heltall $m$. Eller med andre ord, $6^n = 5m+1$.
Bilde
Gjest

Tusen takk for veldig god hjelp!! Kom over enda en oppgave som jeg ikke helt klarer å løse... Synes matematisk induksjon er
vanskelig...

La R være en transitiv relasjon. La [tex]aR^nb[/tex], for n ≥ 1, bety at det finnes en sekvens av tupler

<a0, a1>, <a1, a2>, ..., <an – 1, an>
fra R slik at a0 = a og an = b. Bevis påstanden ”hvis [tex]aR^nb[/tex], så aRb” for alle naturlige tall n ≥ 1 ved matematisk induksjon.
Svar