Skjønner ikke hvordan man klarer å se at $F(n) = T(n) - T(n-1) = 2^{n-1}$.

Basert på et Piazza-spørsmål fra 2019

Oppgaven er å løse rekurrensen

\[T(n) = 3T(n-1) - 2T(n-2)\]

for $n>1$ ($T(0)=0, T(1)=1)$).

Du har fått to hint.

Hint 1: $T(n) - T(n-1) = 2(T(n-1)-T(n-2))$.

Hint 2: La $F(n) = T(n) - T(n-1)$.

Du kan da erstatte $T(n)-T(n-1)$ i det første hintet med $F(n)$ (siden de er like), og du får:

\[F(n) = 2F(n-1)\]

Du har også $F(1) = T(1) - T(0) = 1 - 0 = 1$. Den resulterende rekurrensen er veldig enkel:

\[\begin{aligned} F(n) &= 2F(n-1) \\ &= 4F(n-2) \\ &= 8F(n-3) \\[-1ex] &\hspace{.5em}\vdots \\ &= 2^{n-1} \end{aligned}\]

Vi kan igjen bruke definisjonen \(F(n) = T(n) - T(n-1)\), og ender med:

\[T(n) - T(n-1) = 2^{n-1}\]

som vel var det du lurte på. Det er med andre ord et spørsmål om litt algebra, og å bruke de definisjonene du har fått oppgitt!