Induktion

Hej! Jag är jättedålig på induktion och skulle vilja att någon visar hur jag ska lösa denna med just induktion.
Tack på förhand! (tecken inom {} ska vara nedsänkta).

Definiera följden x{1},x{2},..,x{n},... på följande sätt:

x{1}=3,
x{2}=7 och
x{n+1}=5x{n}-6x{n-1}, n större eller lika med 2.

Visa att x{n}=2^(n)+3^(n-1) för alla n större eller lika med 1.

Sätt y{n} = 2^n + 3^(n-1). Vi ska då visa x{n} = y{n} för alla n större än eller lika med 1.

Basfall n = 1
y{1} = 2^1 + 3^(1-1) = 2 + 1 = 3 = x{1}

Basfall n = 2
y{2} = 2^2 + 3^(2-1) = 4 + 3 = 7 = x{1}

Induktionssteg
Tag N större än eller lika med 1 och antag att y{N} = x{N} och y{N-1} = x{N-1}.
Då gäller x{N+1} = 5 x{N} - 6 x{N-1} = 5 y{N} - 6 y{N-1}
= 5 (2^N + 3^(N-1)) - 6 (2^(N-1) + 3^(N-2))
= (5 * 2^N - 6 * 2^(N-1)) + (5 * 3^(N-1) - 6 * 3^(N-2))
= (5 * 2 * 2^(N-1) - 6 * 2^(N-1)) + (5 * 3* 3^(N-2) - 6 * 3^(N-2))
= (5 * 2 - 6) * 2^(N-1) + (5 * 3 - 6) * 3^(N-2)
= 4 * 2^(N-1) + 9 * 3^(N-2)
= 2^2 * 2^(N-1) + 3^2 * 3^(N-2)
= 2^(N+1) + 3^N
= y{N+1}.
Alltså gäller för fixt N att y{N} = x{N} och y{N-1} = x{N-1} implicerar x{N+1} = y{N+1}.
Eftersom N togs godtyckligt gäller för alla n större än eller lika med 1 att y{n} = x{n} och y{n-1} = x{n-1} implicerar x{n+1} = y{n+1}.

Enligt induktionsprincipen ger basfallen och induktionssteget att x{n} = y{n} för alla n större än eller lika med 1.


Att fundera över: Varför visade jag två basfall?

Hej! Tack för ett bra svar.

Du visade två basfall för att vi har,

x{n+1}=5x{n}-6x{n-1}, n större eller lika med 2 och att vi ska visa
x{n}=2^(n)+3^(n-1) för alla n större eller lika med 1. Tänker jag rätt?

Denna uppgiften känns väldigt mäktig då jag tidigare bara räknat lätta induktionsuppgifter.
Som t.ex. en talföljd som man visar ett basfall på genom att sätta in n=1, sedan ett induktionssteg då man lägger till n+1 och bevisar att VL = HL.

Jag antar att jag är tvungen att lägga till parametern y{n} för att visa att VL=HL?

Sen undrar jag på fjärde raden i induktionssteget:
(5 * 2^N - 6 * 2^(N-1)) + (5 * 3^(N-1) - 6 * 3^(N-2)).

Du har slagit ut parenteserna för att sedan kasta om termerna så att potenser med samma bas ska stå brevid varandra. För att du ser redan då att i senare steg vill du bryta ut potensutrycken.
Stämmer det? Tack igen.

Jag funderade lite mer på detdär med 2 basfall!
Det måste vara så att eftersom x{n+1}=5x{n}-6x{n-1}, n större eller lika med 2, är beroende av två st tal tidigare i talföljden.

Och x{n}=2^(n)+3^(n-1) för alla n större eller lika med 1 är beroende av ett tal tidigare i följden.

Så vi måste ha två basfall för att bevisa detta!

Korrekt.


Den formeln är inte beroende av något tal tidigare i följden. Du har ju inte x{n-...} i högerledet.

Ett klassiskt exempel där man lär sig att det inte alltid räcker med basfall är ju beviset till att alla hästar har samma färg.

Intressant läsning!