Talföljd där ska Visas att T_k är lika med eller mindre än 2^k för alla k=1, 2, 3,...

Hur brukar du göra induktionsbevis med rekursionsformler? Brukar du ha flera olika basfall och antaganden som tillsammans ger beviset för påståendet?

Jag börjar med basfallet och kollar olikheten för k = 1, 2 och 3. Hur går jag tillväga då?

I induktionsantagandet antar jag att $T_{k-2}\le 2^{k-2}, T_{k-1}\le 2^{k-1}, T_k\le 2^k$ för något k ≥ 3. (Eller vi kan skriva p i stället för k)

Sedan visar jag i induktionssteget att $T_k+1\le 2_k+1.$

Verkar det bra och vad har jag kvar att göra?

Lisa Mårtensson skrev:

 

Sedan visar jag i induktionssteget att $T_k+1\le 2_k+1.$

Ser att det blivit fel där.

Det ska stå $T_{k+1}\le 2^{k+1}.$

Har du beräknat det 10-12 första värdena på T? Det är i alla fall vad jag skulle börja med att göra.

Hej!

Steg 1. Visa att $T_1 \leq 2^{1}.$

Steg 2. Låt $k\geq 1$ och anta att $T_k\leq 2^k$. Du vet att det finns åtminstone ett sådant heltal $k.$

Steg 3. Visa att $T_{k+1} \leq 2^{k+1}.$

Steg 4. Enligt Induktionsaxiomet är olikheten sann för alla heltal $k\geq 1.$ 

Steg 1. Det gäller att $T_1 = 1$ och $2^1 = 2$, så olikheten $T_1 \leq 2^{1}$ är samma sak som den sanna olikheten $1 \leq 2.$ 

Steg 3. Eftersom $T_1=1=T_2=T_3$ så är talföljden $(T_k)$ växande. Det medför att 

    $T_{k+1} = T_k+(T_{k-1}+T_{k-2}) \leq T_k + T_{k} = 2T_{k}$

eftersom $T_{k} = (T_{k-1}+T_{k-2}) + T_{k-3}$ och $T_{k-3} \geq 0.$ 

Enligt Steg 2 gäller det att $T_k \leq 2^{k}$ vilket ger att $T_{k+1} \leq 2\cdot 2^{k}.$

Jag visar här hur talföljden ser ut enligt den information som ges i uppgiften. Jag är dock osäker på om jag behöver formulera en explicit formel för talföljden också? Det står ju inte så i frågorna i uppgiften. Skulle ni tro att det kan räcka så här?

Som jag förstått det hela så är formeln för den rekursiva talföljden redan angiven i uppgiften. Men det står att talföljden ska DEFINIERAS så vad kan det innebära att jag ska göra ytterligare?

Talföljden definieras i uppgiften. Du behöver inte hitta ett explicit uttryck (men om det är enkelt skulle det antagligen göra det lättare att bevisa påståendet). 

Jag tror att jag är färdig med uppgiften nu. Tack alla som hjälpt mig.

När jag beskriver induktionssteget på nedanstående sätt fick jag en kommentar från min examinator att det inte räcker för att svara på uppgiften. Han skriver ”varför? ” Meningen som som börjar ”Eftersom $T_1...$ och han har ringat in tecknet $\le$ på raden efter den som börjar ”Eftersom...” 

Det jag vill ha hjälp med att visa är att $T_k+T_{k-1}+T_{k-2}\le 2^{k+1}.$

Hur ska jag göra det?

Tog bort dina citatmarkeringar, som gjorde ditt inlägg svårläsligt. Använd citatmarkeringar endast för citat. /moderator