matematikk.net

En norsklærer som kjeder seg lager ord ved hjelp av figuren nedenfor. Han følger linjene, og skriver ned hver bokstav han passerer (han vender kun ved punktene). Hvert ord han lager har nøyaktig $11$ bokstaver, og alle starter med $A$. To etterfølgende bokstaver kan ikke være like. Hvor mange forskjellige slike ord kan norsklæreren i teorien lage?

Eksempel på mulige ord: $ABRACADABRA$ og $ARADCABARBA$.

Definer $A_n$ som antall lovlige ord på $n$ bokstaver som ender på $A$ og tilsvarende $B_n$
som antall ord på $n$ bokstaver som ikke ender på $A$. Hvis $\omega$ er et ord på $n$
bokstaver som slutter på $A$, gir dette ordet opphav til fire nye ord $\omega R$, $\omega C$,
$\omega D$, $\omega B$, på $n+1$ bokstaver som ikke slutter på $A$. Tilsvarende hvis $\omega$ ikke
slutter på $A$ gir dette opphav til ordene $\omega A$ og $\omega X$, hvor $X$ er en av bokstavene $B$, $C$, $D$
eller $R$ entydig bestemt av siste bokstav i $\omega$. Fra dette argumentet får vi relasjonene
\[A_{n+1}=B_n \mbox{ og } B_{n+1}=4A_n+B_n\]
Vi er ute etter å bestemme $S_n=A_n+B_n$. Observer at $3A_n+B_n=4(A_{n-1}+B_{n-1})$ og dermed
$S_{n+1}=A_{n+1}+B_{n+1}=4A_n+2B_n=(A_n+B_n)+(3A_n+B_n)=S_n+4S_{n-1}$,
altså $S_{n+1}-S_n-4S_{n-1}$. Siden $S_1=1$ og $S_2=4$ kan vi nå regne oss frem til $S_{11}=16376$ ved
hjelp av denne relasjonen.

Løsningen av differensligningen er gitt ved
\[S_n=\left(\frac{3\sqrt{17}+5}{8\sqrt{17}}\right)\left(\frac{1+\sqrt{17}}2\right)^n+
\left(\frac{3\sqrt{17}-5}{8\sqrt{17}}\right)\left(\frac{1-\sqrt{17}}2\right)^n ,\]
men den er ikke veldig effektiv til å regne ut faktiske verdier for $S_n$.