Sterk induksjon oppgave

[hallapaadeg]

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

$a_{0} = 1$
$a_{1} = 3$

Skal vise med sterk induksjon at

$a_{n} = 3^{n}$ for $n \geq 0$

Basis steg...: $n = 0 \Rightarrow a_{0} = 1$ og $3^{0} = 1$ OK

Hypotese...: $a_{j} = 3^{j}$ for $0 \leq j \leq k$, for $k \geq 2$

Induksjonssteg...: $a_{k + 1} = 6a_{(k+1)-1} - 9a_{(k+1)-2} = 6a_{k} - 9a_{k-1} = 2*3*3^{k} - 3^{2} * 3^{k-1} = 2*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*3^{k} - 3^{2} * 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.