Sterk induksjon oppgave

[hallapaadeg]

Har følgen $a_n=6a_{n-1}-9a_{n-2}$, for $n\ge 2$

$a_0=1$
$a_1=3$

Skal vise med sterk induksjon at

$a_n=3^n$ for $n\ge 0$

Basis steg...: $n=0\Rightarrow a_0=1$ og $3^0=1$ OK

Hypotese...: $a_j=3^j$ for $0\le j\le k$, for $k\ge 2$

Induksjonssteg...: $a_{k+1}=6a_{(k+1)-1}-9a_{(k+1)-2}=6a_k-9a_{k-1}=2\ast 3\ast 3^k-3^2\ast 3^{k-1}=2\ast 3^{k+1}-3^{k+1}=3^{k+1}$ ?

Det er det jeg prøvde. Hypotesen er at formelen stemmer for alle heltall $j$ mellom $0$ og $k$, og dette gjør hypotesen sterkere enn å bare anta at formelen stemmer for $et$ vilkårlig tall $k$ som i "vanlig/enkel" induksjon? Jeg er ikke helt sikker på om hypotesen min er riktig og/eller om jeg bruker den riktig.

Jeg ser at svaret mitt er mangelfullt. Er det noen som har lyst til å vise hvordan man fører dette?

[stensrud]

Induksjonssteg... $6a_k-9a_{k-1}=2\ast 3^k-3^2\ast 3^{k-1}$

Du har gjort alt riktig, bare en slurvefeil i induksjonssteget ovenfor: du skriver $6a_k=2\cdot 3^k$, men det skal egentlig stå $6a_k=2\cdot 3\cdot 3^k$.

[hallapaadeg]

Ok takker. Fiksa det for ordens skyld..

Så med sterk induksjon er det egentlig bare hypotesen som ser litt annerledes ut?

[stensrud]

Ja det er riktig; man antar at noe stemmer for ALLE "tidligere" tilfeller, istedenfor å anta at kun det "forrige" tilfellet stemte. Noen ganger holder ikke vanlig induksjon, og da kan det hende sterk funker.