Induktionsbevis

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. $a_{n+1}$ beror på $a_n$ och $a_{n-1}$.

Märk skillnaden jämfört med en explicit (icke-rekursiv) formel, t.ex. $a_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!).

• Talföljden $(a_n)_{n=1}^{\infty}$ är definierad med rekursion eftersom du behöver tidigare termer ($a_{n-1}$ och $a_{n-2}$) för att få det aktuella talet $a_{n}$.
• Talföljden är definierad explicit om det enda du behöver veta är $n$ för att få det aktuella talen $a_n.$

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 $f$ som direkt ger elementen i talföljden via $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

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

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 $2^{n+1}=2·2^n$.

Nej, det stämmer inte. Om n=1 skall värdet bli 1, men din formel ger värdet2¹⁺¹= 2²=4.

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.

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 $f$ som direkt ger elementen i talföljden via $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

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

Det blir väl:

$a_1=\sin 1$

$a_{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. 

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 $a_n=C\cdot k^n$, där $n$ är ett positivt heltal.

Pröva om det stämmer!

Vilka värden på konstanterna $C$ och $k$ passar i så fall in med dina beräknade värden?

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.

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å $a_n$, dels högerledet, där uttrycket ska vara lite lite annorlunda så att du får ut rätt värden.

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

$a_n=\frac{1}{2}·2^n.$

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 a_n=2^n-1.

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

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.

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

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.

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. 

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. 

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.

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

$a_n=2^{n-1}$, 

ska jag då bevisa den för heltal $\ge 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?

Jag väljer att definiera talföljden på ett icke-rekursivt sätt som $a_n=2^{n-1}$.

Nu vill jag bevisa denna form för $a_n$ för alla naturliga tal n$\ge 2$ 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 $a_2$är detsamma som 2 enligt den rekursiva formen vi såg inledningsvis. I högerledet har vi att $2^{2-1}=2^1=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.

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

$\text{VL}=a_1=1=2^0=2^{1-1}=\text{HL}$

Tack, då börjar jag på $a_1.$

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 $$\begin{gathered} n\ge 1, \\ {a}_p=2^{p-1}. \end{gathered}$$

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,

$a_{p+1}=2^{(p+1)-1}=2^p.$

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,

$a_{1+1}=2^{(1+1)-1}\iff a_2=2^1=2.$

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

Lisa Mårtensson skrev:

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

$a_n=2^{n-1}$, 

ska jag då bevisa den för heltal $\ge 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?

$n\ge 2$ gäller för den rekursiva formeln $a_{n+1}$. Men som du ser kan du inte få $a_1$ eller $a_2$ av den med det givna villkoret för n. Så när du ska göra induktionsbeviset för din explicita formel $a_n$ 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 $a_1$ och $a_2$ ä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\in \mathrm{\mathbb{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...

Jag tycker att du har förklarat bra Sabotskij83.

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,

$a_{1+1}=2^{(1+1)-1}\iff a_2=2^1=2.$

$VL=a2=2=2^1=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.

$a_{p+1}=2^{(p+1)-1}=2^p$ så här långt är det rätt. Men om du nu kollar i informationen du fick i uppgiften så ser du att $a_{p+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 $a_{p+1}=2^p$med $a_{p+1}=5a_p-6a_{p-1}$, och sedan ser att vårat induktionsantagande säger att $a_p=2^{p-1}$, så kan vi sätta in det i den rekursiva formeln och försöka lösa för att komma till just $a_{p+1}=2^p$.

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

Det behövs då två basfall och i induktionssteget behövs då två antaganden, ett för $a_n$ och ett för $a_{n+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.

Vi sätter in våra antaganden att $a_p=2^{p-1}$och att $a_{p-1}=2^{p-2}$ i $5a_p-6a_{p-1}$ och ser om det blir lika med $2^p$.

$5·2^{p-1}-6·2^{p-2} = ?$

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

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·2^{3-1}-6·2^{3-2}=5·2^2-6·2=20-12=8$

och $2^3=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.

Lisa Mårtensson skrev:

Vi sätter in våra antaganden att $a_p=2^{p-1}$och att $a_{p-1}=2^{p-2}$ i $5a_p-6a_{p-1}$ och ser om det blir lika med $2^p$.

$5·2^{p-1}-6·2^{p-2} = ?$

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

...

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

Ser detta ok ut?

$$\begin{gathered} 5·2^{p-1}-6·2^{p-2}= \\ =2^{p—2}(5·2-6·1)= \\ =2^{p-2}·(10-6)= \\ =10·2^{p-1}-6^{p-2}= \\ =4·2^{p-2}=2^2·2^{p-1}=2^{p-2+2}=2^p. \end{gathered}$$

På näst sista raden har du missat "$\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?

$$\begin{gathered} 5·2^{p-1}-6·2^{p-2}= \\ =2^{p—2}(5·2-6·1)= \\ =2^{p-2}·(10-6)= \\ =10·2^{p-1}-6^{p-2}= \\ =4·2^{p-2}=2^2·2^{p-1}=2^{p-2+2}=2^p. \end{gathered}$$

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

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

Yngves metod är bättre.

$$\begin{gathered} 5 · 2^{p-1} - 6 · 2^{p-2}= \\ =2^{p-2}(5·2-6·1)= \\ =2^{p-2}·(10-6)= \\ =2^{p-2}·4= \\ =2^{p-2}·2^2= \\ =2^{p-2+2}=2^p. \end{gathered}$$

Lisa Mårtensson skrev:

$$\begin{gathered} 5 · 2^{p-1} - 6 · 2^{p-2}= \\ =2^{p-2}(5·2-6·1)= \\ =2^{p-2}·(10-6)= \\ =2^{p-2}·4= \\ =2^{p-2}·2^2= \\ =2^{p-2+2}=2^p. \end{gathered}$$

Snyggt.

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.