Basfall, visa med induktion

Hej! Jag behöver lite hjälp med basfallet på denna uppgift.

Jag har skrivit om det hela till $2 a_{n - 1} + 1 = 2^{n} - 1 d å n \geq 1$ , och sedan börjar jag ju då med:

steg 1: Basfall. Stoppar in att n=1 och har då $2 a_{0} + 1 = 1$ och här är jag helt förvirrad.

I boken får vi uppgifter som t.ex. Visa att $3^{n} > n^{3} d å n \geq 4$ och då får jag ett mer begripligt basfall i mitt tycke.

Kan jag få något råd om hur jag ska tänka kring just det första steget?

Vad blir a0? tror du?

Hur många flyttningar behöver vi göra om vi inte har någon skiva?

Jag skulle välja n = 2 som basfall.

Smaragdalena skrev:
Jag skulle välja n = 2 som basfall.

Men det står i uppgiften att n>=1.

Jag skulle räkna ut a₁ för hand och betrakta n = 2 som basfall. Det framgår inte från uppgiften vad a₀ skulle betyda.

Jag tolkar det som att man ska flytta på skivorna tills det inte finns någon skiva kvar (n=0) och då behöver man inga flyttningar(a0=0).

Den tolkningen är för teoretisk för mig, därmed inte sagt att den är felaktig.

En till fråga, låt säga att jag har basfall: $2 a_{0} + 1 = 2^{1} - 1 v i l k e t b l i r 1 = 1 d å n \geq 1$

Eftersom $1 \geq 1$ gäller olikheten (med likhet) för n=1

I induktionssteget gör jag antagandet att olikheten gäller för n=p där $p \geq 1$ är ett fixt heltal, dvs att $2 a_{p - 1} + 1 \geq 2^{p + 1} - 1$

Har jag tänkt fel i vänsterledet? För i nästa steg visar jag att olikheten måste vara sann även för n=p+1 och då får jag ju $2 a_{p 0} + 1 \geq 2^{p + 1} - 1$ och detta ser lite komplicerat ut tycker jag, sett till de uppgifter om induktion jag gjort tidigare.

Hur formulerar du ditt induktionsantagande?

Jag förstår inte varför ni diskuterar a_0.

Vi ska vis för n>=1 så basfall är n=1.

Då ska vi alltså visa a_1=2^1-1=1.

Svara

Visa senaste svar