40 svar
408 visningar
Lisa Mårtensson är nöjd med hjälpen!
Lisa Mårtensson 602
Postad: 24 mar 2019

Induktionsbevis

En uppgift som jag ska börja med nu lyder så här:

”Talföljden a1, a2...  är definierad med rekursion enligt följande:

a1=1, a2=2, an+1=5an-6an-1, för n2.

Gissa en icke-rekursiv form för an och bevisa den sedan med induktion.”

Har ni några bra idéer om hur jag bäst bör angripa uppgiften?

Jag har precis börjat lära mig om induktionsbevis, så det är ett nytt område för mig.

Jag undrar också mer precis vad som menas med att ”talföljden ... är definierad med rekursion” ?

AlvinB 3091
Postad: 24 mar 2019

Börja med att skriva ut några element i talföljden och se om du kan hitta ett mönster.

Med en rekursionsformel menas att nästa element i talföljden definieras utifrån de föregående elementen, d.v.s. an+1a_{n+1} beror på ana_n och an-1a_{n-1}.

Märk skillnaden jämfört med en explicit (icke-rekursiv) formel, t.ex. an=n2+1a_n=n^2+1. Här definieras elementen inte utifrån föregående element.

Att talföljden är definierad med rekursion betyder (i det här fallet) att att du behöver veta det första och andra värdet för att kunna beräkna det tredje, det andra och tredje värdet för att beräkna det fjärde och så vidare. Du kan alltså inte beräkna det femtioåttonde värdet utan att först beräkna alla de tidigare värdena.

Börja med att räkna ut sådär ett dussin termer i talföljden. Pricka gärna in dem i  ett diagram, det kan underlätta (men jag lovar inget!).

Albiki 3970
Postad: 25 mar 2019
  • Talföljden (an)n=1(a_n)_{n=1}^{\infty} är definierad med rekursion eftersom du behöver tidigare termer (an-1a_{n-1} och an-2a_{n-2}) för att få det aktuella talet ana_{n}.
  • Talföljden är definierad explicit om det enda du behöver veta är nn för att få det aktuella talen an.a_n.
Albiki 3970
Postad: 25 mar 2019

Ibland kan man översätta mellan rekursiv definition och explicit definition.

Komplicerade talföljder är ofta definierade rekursivt och det är svårt att finna en funktion ff som direkt ger elementen i talföljden via an=f(n)a_n = f(n), vilket är en explicit definition av talföljden.

Ibland kan explicit definierade talföljder vara svåra att definiera rekursivt, exempelvis

    an=esinn ,n1.a_n = e^{\sin n}\ , n\geq 1. (Hur ska man uttrycka ana_n som funktion av tidigare a-värden?)

Lisa Mårtensson 602
Postad: 26 mar 2019

När jag skrivit ut några element i talföljden finner jag mönstret att det efterföljande talet är lika med det föregående gånger två, dvs att talet fördubblas för varje steg i talföljden.

Man kan uttrycka talföljden på en icke rekursiv form som 2n+1=2·2n.

Nej, det stämmer inte. Om n=1 skall värdet bli 1, men din formel ger värdet21+1= 22=4.

Lisa Mårtensson 602
Postad: 27 mar 2019 Redigerad: 27 mar 2019

Ja, jag ser det också. Jag får försöka igen.

Talföljden innebär en exponentiell ökning, visst stämmer det?

Ritar man in talen i talföljden i ett diagram och förbinder talens punkter så att de utgör en kurva, så får man en exponentialfunktions kurva.

Men man ska kanske inte uttrycka talföljden som en exponentialfunktion eftersom det enbart är talen (punkterna i diagrammet) som vi vet något om. Värdena däremellan har vi inte.

tomast80 2376
Postad: 27 mar 2019 Redigerad: 27 mar 2019
Albiki skrev:

Ibland kan man översätta mellan rekursiv definition och explicit definition.

Komplicerade talföljder är ofta definierade rekursivt och det är svårt att finna en funktion ff som direkt ger elementen i talföljden via an=f(n)a_n = f(n), vilket är en explicit definition av talföljden.

Ibland kan explicit definierade talföljder vara svåra att definiera rekursivt, exempelvis

    an=esinn ,n1.a_n = e^{\sin n}\ , n\geq 1. (Hur ska man uttrycka ana_n som funktion av tidigare a-värden?)

Det blir väl:

a1=sin1a_1=\sin 1

an+1=esin1·cosn+ln(an)·cos1a_{n+1}=e^{\sin 1\cdot\cos n+ \ln (a_n)\cdot \cos 1}

En exponentialfunktion är kontinuerlig. Du vill ha en serie, d v s diskreta värden. Du var på rätt spår tidigare, du behöver bara justeta lite. 

Yngve 11701 – Mattecentrum-volontär
Postad: 27 mar 2019 Redigerad: 27 mar 2019
Lisa Mårtensson skrev:

Ja, jag ser det också. Jag får försöka igen.

Talföljden innebär en exponentiell ökning, visst stämmer det?

Ritar man in talen i talföljden i ett diagram och förbinder talens punkter så att de utgör en kurva, så får man en exponentialfunktions kurva.

Men man ska kanske inte uttrycka talföljden som en exponentialfunktion eftersom det enbart är talen (punkterna i diagrammet) som vi vet något om. Värdena däremellan har vi inte.

Det går ofta utmärkt att beskriva en talföljd med hjälp av en funktion. Definitionsmängden är då diskret, vilket i detta fallet innebär att den endast brstår av de positiva heltalen 1, 2, 3 ...

Din gissning är alltså att an=C·kna_n=C\cdot k^n, där nn är ett positivt heltal.

Pröva om det stämmer!

Vilka värden på konstanterna CC och kk passar i så fall in med dina beräknade värden?

Lisa Mårtensson 602
Postad: 27 mar 2019

Det där var lite för svårt för mig att förstå just nu tomast80. Hoppas Albiki svarar och förklarar. 

Undrar just om min explicita talföljd kommer att inbegripa e, sinus eller cosinus? I så fall blir det klurigare än jag hade tänkt mig.

Yngve 11701 – Mattecentrum-volontär
Postad: 27 mar 2019 Redigerad: 27 mar 2019
Lisa Mårtensson skrev:

Det där var lite för svårt för mig att förstå just nu tomast80. Hoppas Albiki svarar och förklarar. 

Undrar just om min explicita talföljd kommer att inbegripa e, sinus eller cosinus? I så fall blir det klurigare än jag hade tänkt mig.

Nej oroa dig inte, du behöver inte ha med dem i din explicita talföljd. Det går utmärkt med de naturliga talen och ett n.

Du var som sagt på rätt spår tidigare med dubbleringen. 

De enda sakerna du behöver ändra är dels vänsterledet, där det bara ska stå ana_n, dels högerledet, där uttrycket ska vara lite lite annorlunda så att du får ut rätt värden.

Lisa Mårtensson 602
Postad: 27 mar 2019

Jag tror nu att jag hittat den icke rekursiva formeln och att den är

an=12·2n.

Nu återstår att bevisa denna formel med induktion.

Jag behöver väl visa på något sätt att den gäller för alla n?

Ja, eller an=2n-1.

Ja, nu skall du visa detta med hjälp av ett induktionsbevis. Vet du hur du skall göra det?

Lisa Mårtensson 602
Postad: 27 mar 2019

Tack Smaragdalena.

Jag får ta mig en titt igen i kurslitteraturen. Jag tycker det kan vara svårt att applicera det jag läser på andra exempel, men jag ska läsa och föreslå något här.

Läs hur man genomför ett induktionsbevis här.

Lisa Mårtensson 602
Postad: 27 mar 2019

Det gick inte att öppna den länken dessvärre.

Sabotskij83 108
Postad: 28 mar 2019 Redigerad: 28 mar 2019

Ett induktionsbevis gör du lättast i fyra steg genom att:

1. Visa att formeln stämmer i ett basfall, förslagsvis n = 2 i detta fall. Då ska H.L = V.L. Detta steget kallas helt enkelt för 'Basfall'. 

2. Anta att likheten stämmer för ett godtyckligt värde på n -- n = p. Detta är ditt 'Induktionsantagande'.

3. Nu ska du visa att likheten även stämmer för n = p + 1. Detta är 'Induktionssteget'.

4. Sammanfatta kort vad du kommit fram till. Gick det att bevisa?

Kan du visa att din formel är sann för basfallet, n = p, och n = p + 1, så har du enligt induktionsprincipen visat att din formel gäller för alla reella värden på n.

Edit: då har du visat att den är sann för alla reella värden på n större än eller lika med det värde du använde i basfallet.

Laguna 5121
Postad: 28 mar 2019
Smaragdalena skrev:

Läs hur man genomför ett induktionsbevis här.

http://www.matteboken.se/lektioner/matte-5/talfoljder-och-induktionsbevis/induktionsbevis

Jag försöker reparera länken. 

Albiki 3970
Postad: 28 mar 2019
Sabotskij83 skrev:

Ett induktionsbevis gör du lättast i fyra steg genom att:

1. Visa att formeln stämmer i ett basfall, förslagsvis n = 2 i detta fall. Då ska H.L = V.L. Detta steget kallas helt enkelt för 'Basfall'. 

2. Anta att likheten stämmer för ett godtyckligt värde på n -- n = p. Detta är ditt 'Induktionsantagande'.

3. Nu ska du visa att likheten även stämmer för n = p + 1. Detta är 'Induktionssteget'.

4. Sammanfatta kort vad du kommit fram till. Gick det att bevisa?

Kan du visa att din formel är sann för basfallet, n = p, och n = p + 1, så har du enligt induktionsprincipen visat att din formel gäller för alla reella värden på n.

Edit: då har du visat att den är sann för alla reella värden på n större än eller lika med det värde du använde i basfallet.

Nej, det man har bevisat är att formeln är sann för alla naturliga tal (n) som är större än 2; det är stor skillnad mot det som du påstår. Det finns många fler reella tal än det finns naturliga tal. 

Sabotskij83 108
Postad: 28 mar 2019
Albiki skrev:
Sabotskij83 skrev:

Ett induktionsbevis gör du lättast i fyra steg genom att:

1. Visa att formeln stämmer i ett basfall, förslagsvis n = 2 i detta fall. Då ska H.L = V.L. Detta steget kallas helt enkelt för 'Basfall'. 

2. Anta att likheten stämmer för ett godtyckligt värde på n -- n = p. Detta är ditt 'Induktionsantagande'.

3. Nu ska du visa att likheten även stämmer för n = p + 1. Detta är 'Induktionssteget'.

4. Sammanfatta kort vad du kommit fram till. Gick det att bevisa?

Kan du visa att din formel är sann för basfallet, n = p, och n = p + 1, så har du enligt induktionsprincipen visat att din formel gäller för alla reella värden på n.

Edit: då har du visat att den är sann för alla reella värden på n större än eller lika med det värde du använde i basfallet.

Nej, det man har bevisat är att formeln är sann för alla naturliga tal (n) som är större än 2; det är stor skillnad mot det som du påstår. Det finns många fler reella tal än det finns naturliga tal. 

Ah, ja naturligtvis har du rätt. Tack för att du rättade det. Förhoppningsvis orsakade inte den fadäsen allt för stor förvirring.

Lisa Mårtensson 602
Postad: 28 mar 2019 Redigerad: 28 mar 2019

I mitt fall, när jag ska bevisa den icke rekursiva formen för an

an=2n-1

ska jag då bevisa den för heltal 2 eftersom man gjorde så med den rekursiva formen.

Alltså, ska det första talet när n=2 i det första steget, induktionsbasen?

Lisa Mårtensson 602
Postad: 28 mar 2019 Redigerad: 28 mar 2019

Jag väljer att definiera talföljden på ett icke-rekursivt sätt som an=2n-1.

Nu vill jag bevisa denna form för an för alla naturliga tal n2 genom induktion och jag börjar med induktionsbasen där jag visar att påståendet gäller för ett basfall, förslagsvis när n=2.

I VL har vi att a2 är detsamma som 2 enligt den rekursiva formen vi såg inledningsvis. I högerledet har vi att 22-1=21=2.

VL är alltså lika med HL, 2=2, och vi har visat att påståendet gäller för det första talet.

Skriv ditt dolda innehåll här

AlvinB 3091
Postad: 28 mar 2019

Ingenting hindrar dig från att börja på a1a_1.

VL=a1=1=20=21-1=HL\text{VL}=a_1=1=2^0=2^{1-1}=\text{HL}

Lisa Mårtensson 602
Postad: 28 mar 2019

Tack, då börjar jag på a1.

Vi gör därefter ett induktionsantagande där vi antar att påståendet gäller för något värde av n, för naturliga tal n1, ap=2p-1.

I induktionssteget visar jag slutligen att om påståendet gäller för något värde av n=p, enligt antagandet, så kommer påståendet att stämma för nästa positiva heltal,

ap+1=2(p+1)-1=2p.

Lisa Mårtensson 602
Postad: 28 mar 2019 Redigerad: 28 mar 2019

Vi kan nu undersöka om påståendet stämmer för nästa positiva heltal, och låta p+1 vara när n=2,

a1+1=2(1+1)-1a2=21=2.

VL=a2=2=21=2(1+1)-1=HL och vi är klara med det tredje och sista steget i vårt induktionsbevis.

Sabotskij83 108
Postad: 28 mar 2019
Lisa Mårtensson skrev:

I mitt fall, när jag ska bevisa den icke rekursiva formen för an

an=2n-1

ska jag då bevisa den för heltal 2 eftersom man gjorde så med den rekursiva formen.

Alltså, ska det första talet när n=2 i det första steget, induktionsbasen?

n2 gäller för den rekursiva formeln an+1. Men som du ser kan du inte få a1 eller a2 av den med det givna villkoret för n. Så när du ska göra induktionsbeviset för din explicita formel an går det bra att använda n = 1 likväl som n = 2. Meningen med basfallet är att visa att likheten stämmer i ett specifikt fall, och då är det kanske mer bekvämt att använda ett specifikt fall som är lätt att verifiera. Eftersom du redan vet vad a1 och a2 är är dem bekväma att börja med. Använder du n = 2 och du kan påvisa resterande steg, så gäller induktionsbeviset för alla n större än eller lika med 2.

Dominoeffekten är ett populärt sätt att beskriva induktionsprincipen. Basfallet är då i princip detsamma som att tippa över en specifik dominobricka för att verifiera att den då faller. Efterkommande steg går ut på att anta att detsamma gäller för vilken dominobricka som helst, n = p, i ledet. Och det tredje steget att visa att; om n = p är sant så är även n = p + 1 sant -- d.s.v. att om en dominobricka faller så faller också nästa dominobricka.

Notera att induktionsbeviset säger egentligen inget om hur vida ditt Induktionsantagande i steg 2 är sant eller inte -- det säger bara att; om n = p är sant, så är även n = p + 1 sant. Men eftersom du med säkerhet i och med basfallet vet att det stämmer i ett specifikt fall, och har visat att det är sant för nästkommande n, så är det sant för alla n.

Hoppas jag inte krånglar till det för dig... du får säga till i så fall så någon lite mer pedagogisk kanske kan förklara. Induktionsbevis brukar vara lite jobb att få grepp om från början...

Lisa Mårtensson 602
Postad: 29 mar 2019 Redigerad: 29 mar 2019

Jag tycker att du har förklarat bra Sabotskij83.

Sabotskij83 108
Postad: 29 mar 2019 Redigerad: 29 mar 2019
Lisa Mårtensson skrev:

Vi kan nu undersöka om påståendet stämmer för nästa positiva heltal, och låta p+1 vara när n=2,

a1+1=2(1+1)-1a2=21=2.

VL=a2=2=21=2(1+1)-1=HL och vi är klara med det tredje och sista steget i vårt induktionsbevis.

Här blir det lite konstigt. Om du låter p + 1 vara när n = 2, så visar du inte riktigt att det stämmer för ett godtyckligt värde på n.

ap+1=2(p+1)-1=2p så här långt är det rätt. Men om du nu kollar i informationen du fick i uppgiften så ser du att ap+1 är formeln för den rekursiva talföljden. Vi har ju antagit att den explicita formeln stämmer för n = p, och n = p ska då också stämma för den rekursiva formeln. Så, om vi substituerar ap+1=2pmed ap+1=5ap-6ap-1, och sedan ser att vårat induktionsantagande säger att ap=2p-1, så kan vi sätta in det i den rekursiva formeln och försöka lösa för att komma till just ap+1=2p.

Lisa Mårtensson 602
Postad: 1 apr 2019 Redigerad: 1 apr 2019

Jag har fått veta nu att jag inte lyckats lösa  denna uppgift korrekt eftersom jag måste använda den givna rekursionen an+1=5an-6an-1.

Det behövs då två basfall och i induktionssteget behövs då två antaganden, ett för an och ett för an+1.

Vilka är nu dessa två basfall och två antaganden?

Vad har jag missat?

 

Jag ska också komma ihåg att hänvisa till induktionsprincipen.

Om induktionsprincipen på matteboken.se:

”Eftersom induktionsprincipen handlar om påståenden som har att göra med naturliga tal större än eller lika med ett startvärde (till exempel 0, 1 eller 2), kan induktionsprincipen visualiseras med hjälp av dominobrickor. Att bevisa någonting med induktion sker i 3 steg.

Visa att påståendet är sant för ett startvärde, till exempel n=1
Antag att påståendet är sant för något heltal n
Visa, med hjälp antagandet i steg 2, att påståendet är sant för heltalet n+1”

Induktionsprincipen har jag förstått handlar om att kunna bevisa att formeln är giltig för all positiva heltal n. Om basfallet är när n=1.

Lisa Mårtensson 602
Postad: 8 apr 2019 Redigerad: 8 apr 2019

Vi sätter in våra antaganden att ap=2p-1 och att ap-1=2p-2 i 5ap-6ap-1  och ser om det blir lika med 2p.

5·2p-1-6·2p-2 = ?

Hur ska jag räkna för att få detta till 2p ?

Jag vet att det ska stämma för när jag sätter in ett värde för p, t.ex. p=3, så stämmer det.

5·23-1-6·23-2=5·22-6·2=20-12=8

och 23=8 så det stämmer för p=3.

Men jag skulle vilja ha hjälp att visa hur det stämmer för det allmänna fallet när vi inte har något bestämt värde på p förutom att det är ett naturligt tals törne än eller lika med 2.

Yngve 11701 – Mattecentrum-volontär
Postad: 8 apr 2019 Redigerad: 8 apr 2019
Lisa Mårtensson skrev:

Vi sätter in våra antaganden att ap=2p-1 och att ap-1=2p-2 i 5ap-6ap-1  och ser om det blir lika med 2p.

5·2p-1-6·2p-2 = ?

Hur ska jag räkna för att få detta till 2p ?

...

Eftersom 2p-1=2·2p-22^{p-1}=2\cdot2^{p-2} så kan du bryta ut den gemensamma faktorn 2p-22^{p-2} ur ditt uttryck.

Lisa Mårtensson 602
Postad: 8 apr 2019

Ser detta ok ut?

5·2p-1-6·2p-2==2p2(5·2-6·1)==2p-2·(10-6)==10·2p-1-6p-2==4·2p-2=22·2p-1=2p-2+2=2p.

På näst sista raden har du missat "·2\cdot2" i den sista termen - men du har räknat vidare som om den fanns där.

Lisa Mårtensson skrev:

Ser detta ok ut?

5·2p-1-6·2p-2==2p2(5·2-6·1)==2p-2·(10-6)==10·2p-1-6p-2==4·2p-2=22·2p-1=2p-2+2=2p.

Det ser bra ut fram till och med rad 3, sen gör du lite slarvfel med exponenterna.

Jag skulle skriva rad 4 som 2p-2·42^{p-2}\cdot 4 och sedan gå vidare därifrån.

Yngves metod är bättre.

Lisa Mårtensson 602
Postad: 8 apr 2019

5 · 2p-1 - 6 · 2p-2==2p-2(5·2-6·1)==2p-2·(10-6)==2p-2·4==2p-2·22==2p-2+2=2p.

Lisa Mårtensson skrev:

5 · 2p-1 - 6 · 2p-2==2p-2(5·2-6·1)==2p-2·(10-6)==2p-2·4==2p-2·22==2p-2+2=2p.

Snyggt.

Lisa Mårtensson 602
Postad: 8 apr 2019

Tack! Äntligen blev jag klar med mitt induktionsbevis, det här var svårt :-)

Lisa Mårtensson skrev:

Tack! Äntligen blev jag klar med mitt induktionsbevis, det här var svårt :-)

I början är allt svårt. Men det blir enklare efter lite övning.

Svara Avbryt
Close