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.
Matematisk induksjon
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
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
Håper noen kan hjelpe
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}$.
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
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
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.
-
Gjest
Tusen hjertelig takk for svar! Det hjelper masse! Hvordan kom du frem til at induksjonshypotesen er 5m + 1?
Hypotesen er at $6^n - 1 = 5m$ for et heltall $m$. Eller med andre ord, $6^n = 5m+1$.
-
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.
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.