012012012

Oplossing van de bonusopgave:

We noemen $f_0(n), f_1(n), f_2(n)$ het aantal goede ternaire strengen van lengte $n$ die respectievelijk eindigen op 0,1,2.

Het is duidelijk dat $f_0(1) = f_1(1) = f_2(1)=1$.
We zullen nu een recursieve formule opstellen om $f_a(n)$ te berekenen.
Stel we kennen de waarde van $f_0(n-1),f_1(n-1),f_2(n-1)$.
Elke rij van lengte $n$ eindigt op 0,1 of 2.
Stel dat hij op 0 eindigt, als we die 0 weglaten wordt het een rij van lengte $n-1$ die op 0,1 en 2 kan eindigen en terug een goede streng is.
Omgekeerd zal het toevoegen van een $0$ aan een goede streng van lengte $n-1$ die eindigt op een $0,1$ of $2$ telkens ook een goede streng opleveren.
Daaruit volgt dat $f_0(n) = f_0(n-1)+f_1(n-1)+f_2(n-1)$.

Analoog zal $f_1(n) = f_0(n-1)+f_2(n-1)$ en $f_2(n) = f_0(n-1)+f_1(n-1)$.
Het is nu duidelijk dat per inductie geldt dat $f_1(n)=f_2(n)$ voor alle $n \in \mathbb N$.
(dit kon ook direct ingezien worden door de symmetrie tussen de enen en twee\"en in de opgave.

bewijs eindigen wijze 1

We kunnen dus een $g(n)$ definiëren zodat $g(n) = \begin{bmatrix} f_0(n)\\f_1(n) \end{bmatrix} = \begin{bmatrix} f_0(n-1) + 2\cdot f_1(n-1) \\f_0(n-1) + f_1(n-1) \end{bmatrix}$
Merk op dat $g(n) = \begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix} \cdot \begin{bmatrix} f_0(n-1) \\f_1(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix} \cdot g(n-1)$.
Per inductie volgt dat $g(n) = \begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix}^{n-1} \cdot g(1) = \begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix}^{n-1} \cdot \begin{bmatrix} 1 \\1 \end{bmatrix}$.

Als we de eigenvectoren van $\begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix}$ berekenen, komen we uit op $\begin{bmatrix} \sqrt{2} \\ 1 \end{bmatrix}$ met $\lambda = 1+\sqrt{2}$ en $\begin{bmatrix} \sqrt{2} \\ -1 \end{bmatrix}$ met $\lambda = 1-\sqrt{2}$
We kunnen $\begin{bmatrix} 1 \\1\end{bmatrix}$ schrijven als een lineaire combinatie van de juist gevonden eigenvectoren. We kunnen door een stelsel uit te werken uit komen dat $\begin{bmatrix} 1 \\1\end{bmatrix} = \frac{\sqrt{2}+2}{4} \cdot \begin{bmatrix} \sqrt{2} \\ 1 \end{bmatrix} + \frac{\sqrt{2}-2}{4} \cdot \begin{bmatrix} \sqrt{2} \\ -1 \end{bmatrix}$

Hierdoor weten we dat $g(n) =\begin{bmatrix} 1 & 2 \\1 & 1 \end{bmatrix}^{n-1} \cdot \begin{bmatrix} 1 \\1 \end{bmatrix}$ gelijk is aan $$ \frac{\sqrt{2}+2}{4}\cdot(1+\sqrt{2})^{n-1}\cdot \begin{bmatrix} \sqrt{2} \\ 1 \end{bmatrix} + \frac{\sqrt{2}-2}{4}\cdot(1-\sqrt{2})^{n-1}\cdot \begin{bmatrix} \sqrt{2} \\ -1 \end{bmatrix}$$ wegens de definiërende eigenschap van eigenvectoren.
Het totaal aantal mogelijkheden goede ternaire strengen van lengte $n$ is natuurlijk $f_0(n) + f_1(n) + f_2(n) = f_0(n) + 2\cdot f_1(n) $ wat kan uitgewerkt worden tot $$\frac{1}{2}\left((1-\sqrt{2})^{n+1} + (1+\sqrt{2})^{n+1}\right).$$

Voor $n=10$ krijgen we $8119$ mogelijkheden.

bewijs eindigen wijze 2, zonder (rechtstreekse) lineaire algebra

Stel $f(n)=f_0(n)+2f_1(n)$.
Dan is $f(1)=3$ en $f(2)=7$.
Merk op dat $f_0(n)=f(n-1)$ en dus $2f_1(n)=f(n)-f(n-1)$.
Dit betekent dat $f(n) = f_0(n-1)+2 \cdot f_1(n-1)= 2f(n-1)-f(n-2)$.

De karakteristieke veelterm van deze recursie is $x^2-2x-1$ en heeft nulpunten $\lambda_{1,2} = 1\pm \sqrt{2}$, waarna we terug kunnen vinden dat
$$f(n)=\frac{1}{2}\left((1-\sqrt{2})^{n+1} + (1+\sqrt{2})^{n+1}\right).$$