Diskret matematik
Hej, jag skulle uppskatta om någon kan säga om mitt svar är korrekt. Om det inte är korrekt då vad är det korrekta svaret.
Jag har ingen aning vad "stark" induktion är, men du har verifierat att F(n)=3^n för n=0 och 1.
Vi skall visa att
2F(n-1)+3F(n-2) = 3^n för n=0,1,...
Induktionsantagande: Antag att F(k)=3^k för k=0, 1, 2, ..., n-2.
Vi har att
VL(n) = 2F(n-1)+3F(n-2) = //induktionsantagandet// =2*3^(n-1) + 3*3^(n-2) =2/3 *3^n + 3/9 *3^n =2/3 *3^n + 1/3 *3^n = *3^n = F(n) = HL(n)
Alltså gäller antagandet enligt induktionsaxiomet.
Trinity2 skrev:Jag har ingen aning vad "stark" induktion är, men du har verifierat att F(n)=3^n för n=0 och 1.
Vi skall visa att
2F(n-1)+3F(n-2) = 3^n för n=0,1,...
Induktionsantagande: Antag att F(k)=3^k för k=0, 1, 2, ..., n-2.
Vi har att
VL(n) = 2F(n-1)+3F(n-2) = //induktionsantagandet// =2*3^(n-1) + 3*3^(n-2) =2/3 *3^n + 3/9 *3^n =2/3 *3^n + 1/3 *3^n = *3^n = F(n) = HL(n)
Alltså gäller antagandet enligt induktionsaxiomet.
Tack för snabba svaret 🙏
Är också nyfiken på vad "stark" induktion är. Skiljer detta sig från ett vanligt induktiondbevis?
Tillägg: 29 dec 2021 23:45
Verkar vara en variant men jag hsde bara kallat detta för ett induktionsbevis.
"Strong induction is a variant of induction, in which we assume that the statement holds for all values preceding k. This provides us with more information to use when trying to prove the statement"
Dracaena skrev:Är också nyfiken på vad "stark" induktion är. Skiljer detta sig från ett vanligt induktiondbevis?
Tillägg: 29 dec 2021 23:45
Verkar vara en variant men jag hsde bara kallat detta för ett induktionsbevis.
"Strong induction is a variant of induction, in which we assume that the statement holds for all values preceding k. This provides us with more information to use when trying to prove the statement"
Ja precis, på enkel induktion behöver man bara visa basfallet och inga mer steg och därför är kortare men på stark induktion behöver man ha mera beräkningar och därmed funkar alltid (Enkel induktion räcker ej i vissa fall). Kolla på bilden!
