Induktionsbevis for en rekursivt definerad talföljd 2
Definera talföljden a(n) genom:
a0 = 3,
a1 = 7,
a(n) = 6a(n-1) - 5a(n-2) för n större eller lika med 2
Jag ska bevisa med induktion att an = 5^n + 2. Det jag gjorde var att konstruera ett formel för a(n+1) = an + 4*5^n. Sedan bevisade jag bara att den gav samma resultat som 5^n + 2 för ett n lika med p+1. Men jag fick noll poäng för hela lösningen för följande anledningar: "a(p+1) funkar inte eftersom man behöver påståendet för p, p-1 för att visa det nästa" och "ap = 4*5^p är inte hur rekursionen definerades".
Hur ska uppgiften egentligen lösas? Regeln med induktion är ju att man ska visa att vårt påstående stämmer för p + 1 också. Att det är en stark induktion säger mig inte så mycket för att jag förstår inte hur det kan ändra lösningen jämfört med om det vore en svag induktion
Hur konstruerade du formeln a(n+1) = a(n) +4*5^n?
Laguna skrev:Hur konstruerade du formeln a(n+1) = a(n) +4*5^n?
Jag prövade mig fram, testade för alla värden, gav samma som 6a(n-1) - 5a(n-2)
Hur ska man beräkna t.ex. a1 med hjälp av din rekursivt definierade följd?
Alla oändligt många värden?
Din formel stämmer kanske, men då måste du bevisa att den stämmer både med den givna rekursionsformeln och den givna slutna formeln.
Laguna skrev:Alla oändligt många värden?
Din formel stämmer kanske, men då måste du bevisa att den stämmer både med den givna rekursionsformeln och den givna slutna formeln.
Men om vi säger att den inte stämmer för den slutna formeln isf, hur ska uppgiften lösas?
Vi antar att den stämmer för n = p och n = p-1. Alltså a(p) = 5^p + 2 och a(p-1) = 5^(p-1) + 2.
Då är a(p+1) = 6a(p) - 5a(p-1) = 6(5^p + 2) - 5(5^(p-1) + 2), och nu ska vi förenkla det här till 5^(p+1) + 2, i så fall har vi lyckats.
Laguna skrev:Vi antar att den stämmer för n = p och n = p-1. Alltså a(p) = 5^p + 2 och a(p-1) = 5^(p-1) + 2.
Då är a(p+1) = 6a(p) - 5a(p-1) = 6(5^p + 2) - 5(5^(p-1) + 2), och nu ska vi förenkla det här till 5^(p+1) + 2, i så fall har vi lyckats.
Har kollat i lösningsförslagen och där har de inte använt p + 1 alls
Varför frågar du hur den ska lösas om du har ett lösningsförslag?
Laguna skrev:Varför frågar du hur den ska lösas om du har ett lösningsförslag?
Jag förstår dock inte hur det går till, och lösningsförslagen var endast till liknande uppgifter. De sätter något intervall för p och sedan istället för att bevisa för p+1 så bevisar de för n
Har du något exempel på ett induktionsbevis som du tycker att du förstår?
Laguna skrev:Har du något exempel på ett induktionsbevis som du tycker att du förstår?
Bevisa uttryck för summor, induktion med modulo och uppgifter som 3p < 3^p brukar jag inte ha problem med
Om de använder n och p på ett annat sätt så kanske du kan göra om min bevisbörjan så att den stämmer med hur det brukar se ut.
