Induktionsbevis - induktionsteget

Talföljden $T_{1}, T_{2}, T_{3} . . .$ definieras genom att sätta $T_{1} = T_{2} = T_{3} = o c h T_{k + 1} = T_{k} + T_{k - 1} + T_{k - 2} .$

Jag ska visa att $T_{k} \leq 2^{k}$ för alla k=1, 2, 3,...

1. Basfall

$T_{1} = 1 o c h 2^{1} = 2$ så olikheten $T_{1} \leq 2^{1}$ är samma sak som den sanna olikheten $1 \leq 2 .$

$T_{2} = 1 o c h 2^{2} = 4 . . . . . . . . d e n s a n n a o l i k h e t e n 1 \leq 4 . T_{3} = 1 o c h 2^{3} = 8 . . . . . . . . d e n s a n n a o l i h e t e n 1 \leq 8 .$

2. Induktionsatagande

Likheten stämmer för något k större än eller lika med 3, i detta fall att

$T_{k - 2} \leq 2^{k - 2}, T_{k - 1} \leq 2^{k - 1} o c h T_{k} \leq 2^{k}$ för något $k \geq 3 .$

3. Induktionssteget - det är här jag behöver hjälp!

Jag vill här visa att likheten stämmer för nästa positiva heltal, dvs. för k=k+1, vilket är detsamma som att $T_{k + 1} \leq 2^{k + 1} .$

Enligt rekursionsformeln har vi att $T_{k + 1} = T_{k} + T_{k - 1} + T_{k - 2}$ och i och med induktionsantagandet har vi antagit att $T_{k} + T_{k - 1} + T_{k - 2} \leq 2^{k} + 2^{k - 1} + 2^{k - 2} .$

Jag skulle kanske kunna komma vidare i mitt bevis genom att i det sistnämnda uttrycket bryta ut $2^{k - 2}$ i HL?

Då har vi $2^{k - 2} (2^{2} + 2^{1} + 2^{0}) = 2^{k - 2} (2^{2} + 2 + 1) .$

Hur kan jag komma vidare från detta?

Ditt induktionsantagande ser rätt udda ut.

Normalt antar man antingen:

Svag induktion: Olikheten gäller för något k, $T_{k} \leq 2^{k}$ .

eller

Stark induktion: Olikheten gäller för alla för alla k upp till ett visst n, dvs $k \leq n \to T_{k} \leq 2^{n}$ .

Här vill du nog ha stark induktion.

Så, hur är dina tankar kring hur induktionssteget ska se ut?

Induktionsantagandet ska nog vara riktigt, så som jag skrivit, även om man säkert kan göra på olika sätt. Jag vet det eftersom jag fått hälften av uppgiften rättad av en lärare.

Att jag har tre antaganden hänger ihop med att jag har tre basfall.

Men när det gäller induktionssteget har jag problem. Där skulle jag behöva råd och hjälp att visa att $T_{k + 1} \leq 2^{k + 1} .$

Enligt induktionsantagandet gäller att $T_{k} \leq 2^{k} v i l k e t g e r a t t T_{k + 1} \leq 2 \cdot 2^{k} .$

$2^{k} + 2^{k - 1} + 2^{k - 2} \leq 2^{k + 1}$ är alltså vad du ska visa.

Smutsmunnen skrev:
$2^{k} + 2^{k - 1} + 2^{k - 2} \leq 2^{k + 1}$ är alltså vad du ska visa.

Stämmer det verkligen?

Om det är som Smutsmunnen skriver så kan jag bryta ut $2^{k - 2} u r 2^{k + 1} .$

$2^{k + 1} = 2^{k - 2} (2^{3})$

Då har vi i VL: $2^{k - 2} \cdot (2^{2} + 2^{1} + 2^{0}) = 7 \cdot 2^{k - 2}$

och i HL har vi: $2^{k - 2} \cdot (2^{3}) = 8 \cdot 2^{k - 3} .$

$7 \cdot 2^{k - 2} \leq 8 \cdot 2^{k - 3} .$

Ursäkta att jag är lite tjatig med en här uppgiften, men är det någon därute som tycker att mitt resonemang här verkar vettigt?

För om vi har antagit att $T_{k + 1} = T_{k} + T_{k - 1} + T_{k - 2} \leq 2^{k} + 2^{k - 1} + 2^{k - 2}$

och om $2^{k} + 2^{k - 1} + 2^{k - 2} \leq 2^{k + 1}$

då har vi alltså även att $T_{k + 1} \leq 2^{k + 1}$ VSB!

Det ser utmärkt ut.

Tackar, tackar!

Jag ser att jag på två ställen skrivit $2^{k - 3}$ där det ska stå $2^{k - 2}$ .

Det är på det stället där jag beskriver uttrycket i HL.

Svara

Visa senaste svar