Uppgift 5

Ina har fått en talföljd definierad rekursivt enligt följande: \[ a_1 = 1 \text{ och } a_n = 2a_{n-1}+n-2 \text{ då $n>1$}. \] Med denna räknar hon ut att för $n=1,2,3,4,5$ så blir $a_1,\dotsc,a_5$ talen \[ 1, 2, 5, 12, 27. \] Ina gissar att det finns en sluten formel för talen, nämligen $a_n = 2^n - n$. Hon har skrivit ned ett induktionsbevis som bevisar detta nedan, men vissa delar i beviset har försvunnit. Du ska bestämma vad som fattas i luckorna; det som fattas kan vara tal, ord eller matematiska uttryck. Inas bevis:

Vi börjar med basfallen. Det behövs ett basfall, nämligen då $n=$(a). Det är lätt att verifiera att den slutna formeln stämmer överens med definitionen i detta fall.
Induktionsantagande: Antag att $n \geq$(b) och att (c). Vi ska nu visa att $a_{n}=$(d). Från (e) är det givet att \[ a_n = 2a_{n-1}+n-2. \] Högerledet kan nu skrivas om enligt (f), så vi får att \[ a_n = 2\left(\text{\underline{\phantom{MMM}(g)\phantom{MMM}}} \right)+n-2. \] Efter förenkling av högerledet, får vi att $a_{n}=$(h), vilket är vad vi ville visa. Basfallen tillsammans med resonemanget ovan visar att den slutna formeln gäller för alla $n \geq $(i).

Max 5 poäng, och för varje lucka som ej är korrekt bestämd dras 1 poäng. Endast svar för luckorna krävs.