Matrisenøtt

[Gustav]

La $M_n$ være $n\times n$-matrisen med komponenter $m_{i,j}$ slik at følgende gjelder: for $1\le i\le n$ er $m_{i,i}=10$; for $1\le i\le n-1$ er $m_{i+1,i}=m_{i,i+1}=3$; alle andre komponenter er $0$. La $D_n$ være determinanten til $M_n$. Da kan $\sum _{n=1}^{\mathrm{\infty }}\frac{1}{8D_n+1}$ uttrykkes som brøken $\frac{p}{q}$ der $p$ og $q$ er positive og relativt primiske heltall.

Bestem $p+q$.

[Markus]

Veldig kult problem! Er ikke særlig erfaren med lineær algebra enda, men denne krevde ikke så veldig mye lineær algebra heller. Løsningen min er langt ifra rigorøs.

Jeg startet med å skrive ned matrisene for små $n$, og lette etter mønster, pga. de 0 som forekommer forsvinner ganske mange av leddene i determinanten.

$1x1$-matrisen er i simpelhet 10.

$2x2$-matrisen:
$\left(\begin{array}{cc}10& 3\\ 3& 10\end{array}\right)$
Der $det(M_2)=91$

$3x3$-matrisen:
$\left(\begin{array}{ccc}10& 3& 0\\ 3& 10& 3\\ 0& 3& 10\end{array}\right)$
Der $det(M_3)=820$

$4x4$-matrisen:
$\left(\begin{array}{cccc}10& 3& 0& 0\\ 3& 10& 3& 0\\ 0& 3& 10& 3\\ 0& 0& 3& 10\end{array}\right)$
Der $det(M_4)=7381$

Prøvde meg videre med diverse mønster. Observerte etter hvert at $D_2=9D_1+1$, og sjekket i likhet med de andre mønstrene om dette holder videre:
$D_3=9D_2+1⟹820=9\cdot 91+1=819+1=820$ - så det stemmer for $n=3$, hva med $n=4$?
$D_4=9D_3+1⟹7381=9\cdot 820+1=7380+1=7381$
Så, det virker som mønsteret stemmer. Jeg vet dessverre ikke hvordan jeg skal bevise at dette holder. Matrisene vil fortsette å være symmetriske på samme måte som de før når vi beveger oss oppover $n$, som får meg til å tro at mønsteret holder. Jeg antar at dette stemmer slik at jeg kan gå videre. Ønsker gjerne tilbakemelding på hvordan jeg kan bevise dette.

Vi kan nå beskrive determinantene rekursivt, med antakelsen at mønsteret over holder:
$D_{n+1}=9D_n+1$

Som egentlig bare er en inhomogen førstegrads differenslikning i forkledning:
$x_{n+1}=9x_n+1$

Er litt bambi på isen med differenslikninger, så følger den generelle løsningsmetoden gitt i dette dokumentet. For å løse den ser vi først på den homogene versjonen av differenslikningen $x_{n+1}=9x_n$. Vi lar denne følgen denoteres ved $\{x_n^h\}$:
$x_n^h=C\cdot 9^n$, der $C\in \mathbb{R}$

Vi må deretter finne en spesifikk følge av den inhomogene likningen, og denoterer denne ved $\{x_n^s\}$
Gjør deretter en såkalt ansatz, og gjetter denne spesifikke løsningen er konstant siden $2$ (naturligvis) er konstant. Da vil vi altså få en følge på formen $A,A,A,\dots$, dvs at $x_n^s=A$. Settes dette inn i vår opprinnelige likning fås
$A=9A+1⟹A=-\frac{1}{8}⟹x_n^s=-\frac{1}{8}$

Hvis vi nå adderer sammen $\{x_n^h\}$ og $\{x_n^s\}$ får vi den generelle løsningen:
$x_n=x_n^h+x_n^s=C\cdot 9^n-\frac{1}{8}$ der $C\in \mathbb{R}$

Initialibetingelsen $x_0=10$ gjør slik at vi kan bestemme $C$.
$x_0=10⟹10=C-\frac{1}{8}⟹C=\frac{81}{8}$

Og ved innsetting i den generelle løsningen fås
$x_n=\frac{81}{8}{9}^n-\frac{1}{8}=\frac{9^2}{8}{9}^n-\frac{1}{8}=\frac{1}{8}(9^{n+2}-1)$

Nå er den generelle løsningen slik at $x_0$ gir $D_1$, $x_1$ gir $D_2$ osv, ved å gjøre eksponenten en grad mindre, blir formelen med en gang mye mer logisk.
$x_n=\frac{1}{8}(9^{n+1}-1)$

En kan lett ved innsetting verifisere at formelen faktisk fungerer. Vi har nå funnet en formel for $D_n$, altså
$D_n=\frac{1}{8}(9^{n+1}-1)$

Da står vi igjen bare med summen
$\sum _{n=1}^{\mathrm{\infty }}\frac{1}{8D_n+1}=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{8\left(\frac{1}{8}(9^{n+1}-1)\right)+1}=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{9^{n+1}}$

Og denne er bare rutine
$\sum _{n=1}^{\mathrm{\infty }}\frac{1}{9^{n+1}}=\sum _{n=0}^{\mathrm{\infty }}\frac{1}{9^{n+2}}=\frac{\frac{1}{81}}{1-\frac{1}{9}}=\frac{1}{72}$

Og siden $gcd(1,72)=1$ er $1$ og $72$ relativt primiske, slik at svaret blir $\boxed{{\displaystyle p+q=73}}$.

[Gustav]

Svaret ditt er korrekt! Veldig bra!

Trikset når det gjelder determinanten er å observere at $D_n=10D_{n-1}-9D_{n-2}$ ved å utvikle etter første kolonne (Ved å definere $D_0=1$ vil denne ligningen gjelde for $n\ge 2$). Herfra kan man vise at $D_n-D_{n-1}=9^n$. Dermed vil $D_n=9^0+9^1+9^2+...+9^n$

[Markus]

Trikset når det gjelder determinanten er å observere at $D_n=10D_{n-1}-9D_{n-2}$ ved å utvikle etter første kolonne (Ved å definere $D_0=1$ vil denne ligningen gjelde for $n\ge 2$). Herfra kan man vise at $D_n-D_{n-1}=9^n$. Dermed vil $D_n=9^0+9^1+9^2+...+9^n$

Aha!
Forresten, hvor er oppgaven fra?

[Gustav]

Gammel AIME II problem.