Matrisenøtt

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Matrisenøtt

Innlegg Gustav » 20/01-2018 19:13

La $M_n$ være $n\times n$-matrisen med komponenter $m_{i,j}$ slik at følgende gjelder: for $1\leq i\leq n$ er $m_{i,i}=10$; for $1\leq i\leq 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}^{\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$.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4290
Registrert: 12/12-2008 12:44

Re: Matrisenøtt

Innlegg Markus » 21/01-2018 00:52

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:
$\begin{pmatrix}
10 & 3\\
3 & 10
\end{pmatrix}$
Der $\det(M_2)=91$

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

$4x4$-matrisen:
$\begin{pmatrix}
10 & 3 & 0 &0 \\
3 & 10 &3 & 0 \\
0 & 3 &10 & 3\\
0 & 0 & 3 & 10
\end{pmatrix}$
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 \Longrightarrow 820 = 9 \cdot 91 + 1 = 819 + 1 = 820 $ - så det stemmer for $n=3$, hva med $n=4$?
$D_4 = 9D_3+1 \Longrightarrow 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 \Longrightarrow A=-\frac18 \Longrightarrow x_n^s = - \frac18$

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 - \frac18$ der $C \in \mathbb{R}$

Initialibetingelsen $x_0 = 10$ gjør slik at vi kan bestemme $C$.
$x_0 = 10 \Longrightarrow 10 = C - \frac{1}{8} \Longrightarrow 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} \left (9^{n+2} - 1 \right)$

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} \left (9^{n+1} - 1 \right )$

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} \left ( 9^{n+1} - 1 \right )$

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

Og denne er bare rutine
$\sum_{n=1}^{\infty} \frac{1}{9^{n+1}} = \sum_{n=0}^{\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{p+q=73}$.
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Matrisenøtt

Innlegg Gustav » 21/01-2018 02:59

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\geq 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$
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4290
Registrert: 12/12-2008 12:44

Re: Matrisenøtt

Innlegg Markus » 21/01-2018 12:57

Gustav skrev: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\geq 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?
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Matrisenøtt

Innlegg Gustav » 22/01-2018 02:14

Gammel AIME II problem.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4290
Registrert: 12/12-2008 12:44

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 4 gjester