2-stegsinduktion

Så jag har för mig att man ska

1.finna en formel för det rekursiva talföljdet, vet dock inte hur

2. Räkna på basfallet när n=0 och n=1

3. anta att formeln gäller n=k-1 och n=k för något k >1 (=)

Och sen vet jag inte riktigt härifrån, men är det ungefär dem här stegen som gäller eller tänker jag fel?

Ja, du tänker rätt.

Induktion bygger på att du visar att

1) formeln gäller för n=0

2) visa att det gäller för k om k-1 är sant.

I detta fall

n=0

F_3n=0 jämnt, F_3n+1=1 udda F_3n+2=1 udda -> ok

n=k

$F_{3 k} = F_{3 k - 1} + F_{3 k - 2} = F_{3 (k - 1) + 2} + F_{3 (k - 1) + 1} = u d d a + u d d a = j ä m n t$

forsätt sedan för F_3k+1 och F_3k+2

1) uppgiften säger ju att man ska visa för alla heltal $n \geq 1$ , betyder inte det att basfallet då måste vara n=1?

2) Det ser bekant ut men förstå inte riktigt vad du gör här, kan du kanske förklara lite mer i ord så jag vet jag ska göra med $F_{3 k + 1} o c h F_{3 k + 2}$

Serien ser ut så här

$0,1,1,2,3,5,8,13,21...$

Varje tal är alltså summan av de två föregående talen.

Så när n=1 är $F_{3n}=F_{3}=2$ (jämnt)

$F_{3n+1}=F_{3+1}=F_4=3$ (udda)

$F_{3n+2}=F_{3+2}=F_5=5$ (udda)

Så uppenbarligen gäller det för $n=1$

Antag nu att det gäller för något $n$ dvs $F_{3n}$ är jämnt $F_{3n+1},F_{3n+2}$ udda. Vad gäller då för $n+1$ dvs för $F_{3(n+1)}=F_{3n+3}$ osv?

Svara

Visa senaste svar