Induksjonsbevis uten grunntilfelle Skriv et svar


Dette spørsmålet er en metode for identifisering og hindring av automatiserte innsendinger.
Smil
:D :) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode er
[img] er
[flash] er AV
[url] er
Smil er
Emne
   

Utvid visningen Emne: Induksjonsbevis uten grunntilfelle

Re: Induksjonsbevis uten grunntilfelle

Innlegg Gustav » 27/01-2018 21:16

La oss betrakte påstanden $1+3+5+\cdots + (2n-1) \neq n^2+3\quad\forall n\in\mathbb{N}$



Bevis ved motsigelse:

Formelen er gyldig for n=1 siden $1\neq 4$.

Induksjonssteget:

Anta formelen er gyldig for $n=k$. Da er $1+3+5+\cdots + (2k-1) \neq k^2+3$. Anta $1+3+5+\cdots + (2k-1) +(2k+1) = (k+1)^2+3$. Da er $1+3+5+\cdots + (2k-1)=(k+1)^2+3-(2k+1)=k^2+2k+1+3-2k-1=k^2+3$, som er en motsigelse. Ergo er $1+3+5+\cdots + (2n-1) \neq n^2+3$ for alle naturlige tall $n$.

Re: Induksjonsbevis uten grunntilfelle

Innlegg Mattegjest » 27/01-2018 14:41

1 + 3 + 5 + ...........+ ( 2n - 1 ) = summen av dei n første oddetala = n[tex]^2[/tex].

Denne formelen kan vi lett vise ved å bruke summeformelen for aritmetisk rekkje

s[tex]_n[/tex] = (a[tex]_1[/tex] + a[tex]_n[/tex])/2 * n

eller ved induksjon.

Re: Induksjonsbevis uten grunntilfelle

Innlegg Brahmagupta » 27/01-2018 14:31

Aleks855 skrev:Det står ikke helt klart i boka hva man kan konkludere, men slik jeg ser det, så kan man vel bytte ut likhetstegnet med ulikhetstegn i beviset, og heller la det stå som et bevis for at $1+3+5+\cdots + (2n-1) \neq n^2+3 \ \ \forall n\in\mathbb N$, gitt at man viser ulikheten for grunntilfellet $n=1$?


Ja, dette stemmer. Det som videre er verdt å merke seg er at induksjonssteget går igjennom
hvis $n^2+3$ blir byttet ut med $n^2+a$ for en vilkårlig $a\in \mathbb{Z}$. Dermed ved å velge
$a$ slik at påstanden holder for $n=1$, så vil man finne en lukket formel for $\sum_{k=1}^n (2k-1)$.
Dette er jo ikke vanskelig, bare velg $a=0$. Følgelig kommer vi frem til formelen
\[ \sum_{k=1}^n (2k-1)=n^2 \]

Induksjonsbevis uten grunntilfelle

Innlegg Aleks855 » 27/01-2018 14:08

La oss betrakte påstanden $1+3+5+\cdots + (2n-1) = n^2+3$

Under induksjonssteget kan vi lett se at dersom påstanden holder for $n=k$, så vil $1+3+5+\cdots+(2k-1) + (2k+1) = k^2 + 3 + (2k + 1) = (k+1)^2 + 3$.

Så induksjonssteget holder.

Men problemet her er at det er vanskelig å finne et grunntilfelle som påstanden holder for. Vi kan kjapt verifisere at påstanden IKKE holder for $n \in \{1, 2, 3\}$ og man kan sikkert fortsette.

Spørsmålet er jo da om det KAN finnes en $n$ som påstanden holder for, eller om det ikke kan finnes noen.

Det står ikke helt klart i boka hva man kan konkludere, men slik jeg ser det, så kan man vel bytte ut likhetstegnet med ulikhetstegn i beviset, og heller la det stå som et bevis for at $1+3+5+\cdots + (2n-1) \neq n^2+3 \ \ \forall n\in\mathbb N$, gitt at man viser ulikheten for grunntilfellet $n=1$?

Topp

cron