\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{xcolor}
\usepackage{verbatim}
\everymath{\displaystyle}
\usepackage{pgf,tikz,pgfplots}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}

\usepackage{subfigure}

\newcommand{\rank}{\operatorname{rank}}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\res}{res}
\newcommand{\e}{\varepsilon}

\begin{document}

\paragraph{Tartu Ülikooli matemaatikaolümpiaad 2020 | 22.05.2020}
\thispagestyle{empty}
\begin{enumerate}
\item
Olgu $a_1 = 0$ ja $a_{n+1} = \frac{1+4a_n}{10 -9a_n}$ kõigi $n \in \mathbb N$ korral.
Leia $a_{2020}$.
\item
Leia kõik kaks korda diferentseeruvad funktsioonid $f: \mathbb R \to \mathbb R$, mis rahuldavad võrdust
\[
f(x)^2 - f(y)^2 = (x-y)f(x+y)
\]
kõikide $x, y \in \mathbb R$ korral.

\item
Kui palju leidub erinevaid täisarvude paare $(x,y)$, mille korral $x^2 + y^2$ jagub arvuga $49$ ja $1 \leq x,y \leq 2020$? (Loeme paarid $(x,y)$ ja $(y,x)$ võrdseteks.)

\item
Olgu vektorruumil $\mathbb R^n$ antud mingi osaline järjestus $\leq$ (tähistame samamoodi nagu tavalist järjestust hulgas $\mathbb R$), mis on kooskõlas algebraliste tehetega:
kui $x,y,z \in \mathbb R^n$ ja $a,b \in \mathbb R$, kusjuures $x \leq y$ ja $0 \leq a \leq b$, siis ka $ax + z \leq by + z$. Lisaks olgu $\leq$ võrejärjestus: kõigi $x, y \in \mathbb R^n$ korral leiduvad nende supreemum $x \vee y$ ja infiimum $x \wedge y$ selle järjestuse suhtes. Iga $x \in \mathbb R^n$ korral tähistame $|x| := x \vee (-x)$.
\begin{enumerate}
\item Esiteks, tõesta järgmised abiomadused, mis kehtivad kõikide $x,y,z \in \mathbb R^n$ korral:
\begin{enumerate}
\item[$(i)$]
$x + y \vee z = (x+y) \vee (x+z)$,
\item[$(ii)$]
$x+y = x\wedge y + x \vee y$,
\item[$(iii)$]
$x\vee y = -(-x)\wedge(-y)$,
\item[$(iv)$]
$|x| = x \vee 0 + (-x) \vee 0$.
\end{enumerate}
\item
Eeldame, et kehtib keskmise muutuja omadus: kui $x_n, y_n \in \mathbb R^n$ ja $0 \leq y_n \leq x_n$ kõikide $n \in \mathbb N$ korral ning $x_n \to 0$, siis ka $y_n \to 0$. 

Tõesta, et kui $x, x_n \in \mathbb R^n$ ja $|x_n| \leq x$ kõikide $n \in \mathbb N$ korral ning $|x+x_n| \to 2x$, siis ka $x_n \to x$.

\end{enumerate}
\item
Tõesta, et päratu integraal
\[
\int_{-\pi/2}^{\pi/2} \ln (\cos x)\, \mathrm{d}x
\]
koondub ja arvuta selle väärtus.

\item
Olgu antud ruutmaatriks 
\[
A = 
\begin{pmatrix}
0 & 0 & 0 & \dots & 0 & a_0\\
1 & 0 & 0 & \dots & 0 & a_1\\
0 & 1 & 0 & \dots & 0 & a_2\\
& \dots & & \dots & & \dots\\
0 & 0 & 0 & \dots & 1 & a_{n-1}\\
\end{pmatrix}
\]
ja polünoom
\[
q(x) = x^n - a_{n-1}x^{n-1} - a_{n-2} x^{n-2} - \ldots - a_0,
\]
kus $a_0, \dots, a_{n-1}$ on kompleksarvud.
Tõesta, et
\begin{enumerate}
\item
$q(A) = 0$,
\item
iga nullist erineva komplekssete kordajatega polünoomi $p$ korral
maatriks $p(A)$ on pööratav parajasti siis, kui polünoomidel $p$ ja $q$ ei ole ühiseid kompleksseid juuri.
\end{enumerate}
\emph{Märkus. Polünoomi $f(x) = b_0 + b_1 x + \dots + b_n x^n$ korral tähistame $f(A) := b_0I + b_1 A + \dots + b_n A^n$, kus $I$ on ühikmaatriks.
}
\end{enumerate}
\newpage

\textbf{Lahendused}
\begin{enumerate}
\item
Tõestame induktsiooniga, et $a_n = \frac{n-1}{3n+4}$:
\[
a_{n+1} = \frac{1+4a_n}{10 -9a_n} = \frac{3n+4+4(n-1)}{10(3n+4)-9 (n-1)} = \frac{7n}{21n + 49} = \frac{n}{3n+7} = \frac{(n+1)-1}{3(n+1)+4}.
\]
Seega $a_{2020} = \frac{2019}{6064}.$
\item
Diferentseerides võrdust kõigepealt $x$ järgi ja siis $y$ järgi, saame, et
\[
0 = \frac \partial {\partial y}(f(x+y) + (x-y)f'(x+y))
= f'(x+y) - f'(x+y) + (x-y)f''(x+y) = (x-y)f''(x+y).
\]
Järelikult $f''(x) = 0$ iga $x$ korral, mistõttu $f(x) = ax + b$. Asetades selle üldkuju lähtevõrrandisse ja võttes seal $y = 0$, osutub, et
\[
(ax+b)\cdot x = (ax+b)^2 - b^2 = ax (ax + 2b)
\]
ehk
\[
ax + b = a^2x + 2ab 
\]
ehk
\[
a(a-1)x = b - 2ab.
\]
Kuna $x$ on suvaline, peab olema kas $a = 0$ või $a = 1$. Mõlemal juhul $b = 0$. Niisiis lahendid on $f(x) = 0$ ja $f(x) = x$.

\emph{Märkus (Tähvend Uustalu).} Sama lahendihulga saamiseks piisab tegelikult nõuda ainult funktsiooni pidevust.
Nimelt, valides lähtevõrrandis $y=0$, tekib tingimus $f(x)^2-f(0)^2=xf(x)$ ehk
\[
f(x)=\frac{x\pm \sqrt{x^2+4f(0)^2}}{2}.
\]

Kui $f(0)=0$, siis $f(x)=\frac{x\pm|x|}{2}$ ehk $f(x)=0$ või $f(x)=x$ iga konkreetse $x$ korral. Et $f$ peab olema pidev (kogu reaalteljel), on ainsad võimalused $f(x)=0$ ja $f(x)=x$.

On jäänud uurida võimalust $f(0)^2>0$. Ilmselt $|x|<\sqrt{x^2+f(0)^2}$. Seega $\frac{x+ \sqrt{x^2+4f(0)^2}}{2}>0$ ja $\frac{x- \sqrt{x^2+4f(0)^2}}{2}<0$. Et $\frac{x\pm \sqrt{x^2+4f(0)^2}}{2}\ne0$, siis, vältimaks vastuolu Bolzano--Cauchy teoreemiga pideva funktsiooni nullkohast, jääb ainult kaks võimalust:
\begin{align*}
f(x)&=\frac{x+ \sqrt{x^2+4f(0)^2}}{2},\qquad x\in\mathbb{R},\\
f(x)&=\frac{x- \sqrt{x^2+4f(0)^2}}{2},\qquad x\in\mathbb{R}.
\end{align*}
Muuhulgas siis esimesel juhul $f(\pm 1)^2=\frac{2+4f(0)^2\pm 2\sqrt{1+4f(0)^2}}{4}$.
Valides lähtevõrrandis $x=1$ ja $y=-1$, omandab lähtevõrrand kuju
$\sqrt{1+4f(0)^2}=2f(0)$, vastuolu. Analoogne vastuolu tekib ka teisel juhul.


\item
Paneme tähele, et $x^2 + y^2$ jagub $49$-ga parajasti siis, kui nii $x$ kui ka $y$ jaguvad $7$-ga. Tõepoolest, $x^2$ ja $y^2$ saavad omandada ainult jääke $0, 1, -3, 2$ modulo $7$. Niisiis ainus võimalus selleks, et $x^2 + y^2$ annaks jäägi $0$ modulo $7$ on, et nii $x^2$ kui ka $y^2$ annavad jäägi $0$ modulo $7$; nüüd aga nii $x^2$ kui ka $y^2$, seega ka $x^2+y^2$ jagub $49$-ga.

Täisarve, mis jaguvad $7$-ga ja on väiksemad kui $2020$, on $\lfloor 2020/7 \rfloor = 288$ tükki. Vastus on järelikult 
\[
\binom{288}{2}+\binom{288}{1}=\frac{288 \cdot 287}{2} + 288 = \frac{288 \cdot 289}{2} = 41616.
\]
\item
\begin{enumerate}
\item
\begin{enumerate}
\item[$(i)$]
Kuna $x + y \vee z \geq x + y$ ja $x + y \vee z \geq x + z$, saame, et $x + y \vee z \geq (x + y) \vee (x+z)$. Seetõttu
$(x + y) \vee (x+z) - x \geq y \vee z$ ning liites $x$ mõlemale poolele, saame, et $(x + y) \vee (x+z) \geq x + y \vee z$.
\item[$(ii)$] Kasutades $(i)$ nii supreemumite kui ka infiimumite jaoks (mis on kindlasti saadav ka sama tõestusega), saame, et 
\[
x \vee y + x \wedge y = (x + x \wedge y) \vee (y + x \wedge y) = ((2x) \wedge (x+y)) \vee ((y + x) \wedge (2y)) \leq x+y,
\]
sest viimase supreemumi mõlemad argumendid on $\leq x+y$.
Vahetades supreemumite ja infiimumite kohad tõestuses, saame ka teise võrratuse kätte.
\item[$(iii)$] Sarnaselt ülalolevale, üks osa sümeetrilisest tõestuses käib järgmiselt:
\[
x \vee y + (-x) \wedge (-y) = (x + (-x) \wedge (-y)) \vee (y + (-x) \wedge (-y)) = (0 \wedge (x-y)) \vee ((y - x) \wedge 0) \leq 0.
\]
\item[$(iv)$]
Tähistame $x^+ = x \vee 0$ ja $x^- = (-x) \vee 0$ ning märgime, et 
\[
x^+ + x^- = x \vee 0  + (-x) \vee 0 = (x \vee 0 -x) \vee (x \vee 0) = 0 \vee (-x) \vee x \vee 0  = |x| \vee 0.
\]
Jääb veenduda, et $|x| \geq 0$. Selleks paneme tähele, et
\[
2|x| = x\vee (-x) + (-x)\vee x = (x-x)\vee (-2x) \vee (2x) \vee (-x + x) = 0 \vee (-2x) \vee (2x) \vee 0 \geq 0
\]
ja jagame kahega.
\end{enumerate}
\item
Kõigepealt paneme tähele, et
$x^+ - x^- = x \vee 0 - (-x) \vee 0 = x \vee 0 + x \wedge 0 = x + 0 = x$.
Meie eeldusest $|x_n| = x^+ + x^- \leq x$ järeldub, et $x \geq x_n^+, x_n^- \geq 0$.
Paneme tähele, et
\[
|x + x_n| = |x + x_n^+ - x_n^-| = (x + x_n^+ - x_n^-) \vee (x_n^- -x - x_n^+) \leq (x + x_n^+ ) \vee x_n^- = x + x_n^+ \leq 2x,
\]
seega
\[
2x - |x + x_n| \geq 2x - x + x_n^+ \geq 0.
\]
Keskmise muutuja omadus annab nüüd, et $x + x_n^+ \to 2x$, millest $x_n^+ \to x$.
Nüüd
\[
0 \leq x_n^- = |x_n| - x_n^+ \leq x - x_n^+ \to 0
\]
ja järjekordne keskmise muutuja omaduse rakendamine annab, et $x_n^- \to 0$. Seega,
\[
x_n = x_n^+ - x_n^- \to x.
\]
\emph{Märkus.} Mõned võistlejad märkasid, et ülesande tekst on vigane. Nimelt, algebraliste tehetega kooskõla tingimuses peaks nõudma, et $0 \leq x \leq y$ (oli ainult $x \leq y$).
Teksti hoolikal lugemisel saab võrdlemisi kiirelt aru, et selliseid osalisi järjestusi ei leidu. Kuna osa võistlejaist sai aru, mis pidi olema õige ülesanne ja hakkasid lahendama hoopis seda, otsustasime, et me ei annulleeri seda ülesannet, aga ka pelgalt selle vea esile tõstmise eest täispunkte ei anna. Anname aga vähemalt pool ülesande punktide arvust ehk täpsemalt $\max(10, \text{õige ülesande lahenduse punktid})$.
\end{enumerate}

\item
\emph{Lahendus 1.}
Tähistame ülesande integraali sümboliga $I$.
Teeme muutuja vahetuse $y = x + \pi/2$; kuna funktsioon $\ln \cos x$ on paaris, siis
\[
I = \int_0^\pi \ln\sin y \,\mathrm{d}y \quad \mbox{ja} \quad 
\int_0^{\pi/2} \ln\cos x \,\mathrm{d}x = \int_{-\pi/2}^0 \ln\cos x \,\mathrm{d}x = \int_0^{\pi/2} \ln\sin y \,\mathrm{d}y.
\]
Oletades, et ülesande integraal on koonduv, leiame tema väärtuse.
\begin{align*}
I &= \int_0^{\pi/2} \ln\sin y \,\mathrm{d}y + \int_0^{\pi/2} \ln\cos x \,\mathrm{d}x = \int_0^{\pi/2} \ln(\sin x \cos x) \,\mathrm{d}x
= \int_0^{\pi/2} \ln\frac{\sin(2x)}{2} \,\mathrm{d}x\\
&= \frac 1 2  \int_0^{\pi} (\ln(\sin x)  - \ln 2)\,\mathrm{d}x
= \frac I 2 - \frac{\pi \ln 2}{2}.
\end{align*}
Niisiis $I = -\pi \ln 2$.

Koonduvuse tõestamiseks paneme tähele, et kui arvud $0 < a < b$ on piisavalt väikesed, siis
\[
\int_a^b \ln\sin x\,\mathrm{d}x \geq \int_a^b \ln(x^2) \,\mathrm{d}x = 
\int_a^b 2\ln x \,\mathrm{d}x = 2(x\ln(x)-x)\Big|_a^b = C_b - 2a\ln a + a.
\]
Järelikult l'Hospitali reegli põhjal
\[
\int_0^b \ln\sin x \,\mathrm{d}x = \lim_{a \to 0+}
\int_a^b \ln\sin x \,\mathrm{d}x \geq \lim_{a \to 0+}
C_b - 2a\ln a + a = \lim_{a \to 0+}
C_b + 2a = C_b.
\]
Kuna $\ln\sin x < 0$, on koondumine monotoonne, millest piisab -- piirväärtuse all on kahanev alt tõkestatud suurus.

\emph{Lahendus 2 (Heiki Niglas).}
Teostame järgmised teisendused (kõik päratud integraalid koonduvad või hajuvad samaaegselt):
\begin{align*}
\int_{-\frac\pi2}^{\frac\pi2}\ln\cos x\,\mathrm{d}x&=2\int_0^{\frac\pi2}\ln\cos x\,\mathrm{d}x=\\
&=-\int_0^{\frac\pi2}\ln\frac1{(\cos x)^2}\,\mathrm{d}x=\\
&=-\int_0^{\frac\pi2}\ln((\tan x)^2+1)\,\mathrm{d}x=\\
&\mathop{=}^{t=\tan x}-\int_0^\infty\frac{\ln(t^2+1)}{t^2+1}\,\mathrm{d}t.
\end{align*}

Vaatleme kompleksmuutuja funktsiooni $f(z)=\frac{\ln(z+\mathrm{i})}{z^2+1}$. Sellel on esimest järku poolused punktides $z=\pm\mathrm{i}$. Vaatleme kontuuri $C$, mis on moodustatud ringjoone kaarest $C_R$ punktidega $R\cos u + \mathrm{i}R\sin u$, kus $u=0\ldots \pi$, ja lõigust $[-R,R]$ punktidega $u+0\mathrm{i}$, kus $u=-R\ldots R$.
Resiidide teooria põhiteoreemi kohaselt
\begin{align*}
\int_C f(z)\,\mathrm{d}z&=2\pi \mathrm{i}\res[f(z),\mathrm{i}]=\\
&=2\pi \mathrm{i}\lim_{z\to\mathrm{i}}(z-\mathrm{i})\frac{\ln(z+\mathrm{i})}{(z+\mathrm{i})(z-\mathrm{i})}=
2\pi \mathrm{i}\cdot\frac{\ln(2\mathrm{i})}{2\mathrm{i}}=2\pi \mathrm{i}\cdot \frac{\ln 2+\frac\pi4\mathrm{i}}{2\mathrm{i}}=\\
&=\pi\ln 2+\frac{\pi^2}{2}\mathrm{i}.
\end{align*}

Minnes piirile $R\to\infty$, kehtib $\lim_{R\to\infty}\int_{C_R} f(z)\,\mathrm{d}z=0$ tänu Jordani lemmale, sest
$\lim_{\substack{z\to\infty\\\mathrm{Re}\,z\geq0}}zf(z)=0$.
Niisiis 
\[
\lim_{R\to\infty}\int_{-R}^R\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z=\pi\ln 2+\frac{\pi^2}{2}\mathrm{i}.
\]

Järgneva võrdusteahela teises liidetavas teeme muutuja vahetuse $z\mapsto -z$:
\begin{align*}
\int_{-R}^R\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z&=\int_0^R\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z+\int_{-R}^0\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z=\\
&=\int_0^R\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z+
\int_0^R\frac{\ln(-z+\mathrm{i})}{z^2+1}\,\mathrm{d}z=\\
&=\int_0^R\frac{\ln(\mathrm{i}^2-z^2)}{1+z^2}\,\mathrm{d}z=\\
&=\int_0^R\frac{\ln(-1)+\ln(1+z^2)}{1+z^2}\,\mathrm{d}z=\\
&\mathop{=}^{\mathrm{e}^{\mathrm{i}\pi}=-1}\mathrm{i}\int_0^R\frac{\pi}{z^2+1}\mathrm{d}z+\int_0^R\frac{\ln(z^2+1)}{z^2+1}\,\mathrm{d}z,
\end{align*}
kusjuures saadud summa on vaadeldava kompleksarvu algebraline kuju (esimene liidetav on imaginaarosa ja teine on reaalosa, sest integraalid on reaalsed).

Kokkuvõttes
\begin{align*}
\int_0^\infty\frac{\ln(t^2+1)}{t^2+1}\,\mathrm{d}t
&=\lim_{R\to\infty}\int_0^R\frac{\ln(z^2+1)}{z^2+1}\,\mathrm{d}z=\\
&=\lim_{R\to\infty}\mathrm{Re}\,\int_{-R}^R\frac{\ln(z+\mathrm{i})}{z^2+1}\,\mathrm{d}z=\\
&=\lim_{R\to\infty}\mathrm{Re}\,\left(\pi\ln 2+\frac{\pi^2}{2}\mathrm{i}\right)=\\
&=\pi\ln 2
\end{align*}
ja seega
\[
\int_{-\frac\pi2}^{\frac\pi2}\ln\cos x\,\mathrm{d}x=
-\int_0^\infty\frac{\ln(t^2+1)}{t^2+1}\,\mathrm{d}t=-\pi\ln 2.
\]

\emph{Märkus.} Integraali $\int_0^\infty\frac{\ln(t^2+1)}{t^2+1}\,\mathrm{d}t$ arvutamiseks
pakutakse leheküljel \textsf{stackexchange.com} veel mitmeid võimalusi. Loetleme siin mõne täiendava idee:
\begin{itemize}
\item Tähistame $I(\alpha)=\int_0^\infty\frac{\ln(t^2+\alpha)}{t^2+1}\,\mathrm{d}t$. Tegu on päratu parameetrist sõltuva integraaliga. Kuna $I(\alpha)$ on koonduv ja $\int_0^\infty\frac{\partial}{\partial\alpha}\frac{\ln(\alpha t^2+1)}{t^2+1}\,\mathrm{d}t=\int_0^\infty\frac{1}{( t^2+\alpha)(t^2+1)}\,\mathrm{d}t$ on ühtlaselt koonduv igas lõigus $[\alpha_0,2]$, kus $\alpha_0>0$, siis $I'(\alpha)=\int_0^\infty\frac{1}{(t^2+\alpha)(t^2+1)}\,\mathrm{d}t=\frac{\pi}{2(\sqrt{\alpha}+\alpha)}$, mistõttu $I(\alpha)=\pi\ln(1+\sqrt{\alpha})+C$. Arvutades vahetult $I(0)=\lim_{\alpha\to0+}I(\alpha)$, leiame, et $C=0$. Integraali väärtus on $I(1)=\pi\ln2$.

\item Analoogiliselt saame arutleda, kui valime $I(\alpha)=\int_0^\infty\frac{\ln(\alpha t^2+1)}{t^2+1}\,\mathrm{d}t$.

\item Tähistades hoopis $I(\alpha)=\int_0^\infty (1+t^2)^{\alpha-1}\,\mathrm{d}t$, saame samal moel integraali märgi all diferentseerides, et ühelt poolt $I'(0+)=\int_0^\infty\frac{\ln(t^2+1)}{t^2+1}\,\mathrm{d}t$, teiselt poolt aga asendus $t=\tan \theta$ annab, et
$I(\alpha)=\int_0^{\frac\pi2} \frac{\mathrm{d}\theta}{(\cos \theta)^{2\alpha}}=\frac12 B\left(\frac12,\frac12-a\right)=\frac{\sqrt\pi}{2}\cdot\frac{\Gamma(\frac12-\alpha)}{\Gamma(1-\alpha)}$.
Teostame logaritmilise diferentseerimise: $I'(\alpha)=I(\alpha)\cdot(\ln I(\alpha))'=-I(\alpha)\cdot\left(\psi\left(\frac12-\alpha\right)-\psi(1-\alpha)\right)$, kus $\psi(x)=(\ln I(\alpha))'$. Nüüd $I'(0)=-\frac\pi2\cdot\left(\psi\left(\frac12\right)-\psi(1)\right)$. Sulgudes asuva teguri väärtuse arvutame võrduse $\frac{\psi(a)-\psi(b)}{a-b}=\sum_{n=0}^\infty \frac{1}{(n+a)(n+b)}$ abil (see võrdus järeldub gammafunktsiooni $\Gamma$ ja digammafunktsiooni $\psi$ omadustest; paremal on teleskoopsumma, sest $\frac1{(n+\frac12)(n+1)}=\frac{2}{n+\frac12}-\frac{2}{n+1}$).

\item Võrdusest $\prod_{k=1}^{n-1}\sin\frac{\pi k}{n}=\frac{2n}{2^n}$ (saab tõestada näiteks ühejuuri kasutades) järeldub Riemanni summade kaudu, et
\[
\int_0^\pi \ln\sin x\,\mathrm{d}x=\lim_{n\to\infty}\frac\pi n\sum_{k=1}^{n-1}\ln\sin\frac{\pi k}{n}=\lim_{n\to\infty}\frac\pi n\ln\frac{2n}{2^n}=-\pi\ln 2.
\]

\item Kasutame Fourier' reaksarendust
\[
\ln\cos x=-\ln 2+\sum_{k=1}^\infty (-1)^{k-1}\frac{\cos 2k x}{k}
\]
(selleni saab jõuda ka koosinuse komplekskuju ja kompleksse logaritmi Taylori valemi kaudu)
ning integreerime liikmeti.

\end{itemize}


\item
\begin{enumerate}
\item
Väite tõestame nii, et näitame: lineaarteisendus $q(A)$ viib kõik baasivektorid (s.t. ühikmaatriksi veerud) $e_i$, $0 \leq i \leq n-1$, nullvektoriks.
Märgime, et $Ae_i = e_{i+1}$ kõigi $i < n-1$ ja $Ae_{n-1} = \sum_{i=0}^{n-1} a_i e_i =: a$ korral, seega $A^ke_i = e_{k+i} = A^{k+i} e_0$, kui $k+i < n$. Nüüd saamegi, et
\[
q(A)e_0 = A^ne_0-\sum_{i=0}^{n-1}A^i e_0=a - \sum_{i=0}^{n-1} a_i e_i = 0
\]
ja
\[
q(A)e_i = q(A)A^i e_0 = A^iq(A)e_0 = 0
\]
kõigi $i < n$ jaoks.
\item
Piisavus. Ülesandes toodud eeldus juurte kohta tähendab, et polünoomid $p$ ja $q$ on ühistegureita. Kasutades laiendatud Eukleidese algoritmi, saame leida polünoomid  $f$ ja $g$ nii, et kehtib nn. B\'ezout' samasus
\[
pf + qg = 1.
\]
Nüüd $p(A)f(A) + q(A) g(A) = I$. Ent a)-osa põhjal $q(A) = 0$, millest $p(A)f(A) = I$. Järelikult $p(A)$ on pööratav lineaarteisendus.

Tarvilikkus. Arvutame välja maatriksi $A$ karakteristliku polünoomi:
\[
\phi(\lambda) = |A - \lambda I| = 
\begin{vmatrix}
-\lambda & 0 & 0 & \dots & 0 & a_0\\
1 & -\lambda & 0 & \dots & 0 & a_1\\
0 & 1 & -\lambda & \dots & 0 & a_2\\
\dots & \dots & \dots & \dots & \dots & \dots\\
0 & 0 & 0 & \dots & -\lambda & a_{n-2}\\
0 & 0 & 0 & \dots & 1 & a_{n-1} - \lambda\\	
\end{vmatrix}.
\]
Liidame esimesele reale elementidega $\lambda, \lambda^2, \dots, \lambda^{n-1}$ korrutatud ülejäänud read ning saame, et
\[
\phi(\lambda) = 
\begin{vmatrix}
0 & 0 & 0 & \dots & 0 & \sum_{i=0}^{n-1}a_i \lambda^i - \lambda^n\\
1 & -\lambda & 0 & \dots & 0 & a_1\\
0 & 1 & -\lambda & \dots & 0 & a_2\\
\dots & \dots & \dots & \dots & \dots & \dots\\
0 & 0 & 0 & \dots & -\lambda & a_{n-2}\\
0 & 0 & 0 & \dots & 1 & a_{n-1} - \lambda\\	
\end{vmatrix}
= (-1)^{n+1} \left(\sum_{i=0}^{n-1}a_i \lambda^i - \lambda^n\right) = (-1)^n q(\lambda).
\]
Järelikult on polünoomide $p$ ja $q$ ühine juur $\lambda_0$ ühtlasi maatriksi $A$ karakteristliku polünoomi juur ning talle vastab mingi omavektor $x_0 \neq 0$. Niisiis $Ax_0=\lambda_0 x_0$.
Tähistanud $p(x) = \sum_{i=0}^m b_i x^i$, saame, et
\[
p(A)x_0 = \sum_{i=0}^m b_i A^i x_0 = \sum_{i=0}^m b_i \lambda_0^i x_0 = p(\lambda_0) x_0 = 0.
\]
Oleme leidnud, et $p(A)$ viib nullist erineva vektori nullvektoriks ega saa seetõttu olla pööratav.
\end{enumerate}

\emph{Märkus 1.} Arvutanud antud lineaarteisenduse karakteristliku polünoomi $(-1)^nq(\lambda)$, järeldub kohe Cayley--Hamiltoni teoreemi kohaselt, et $q(A)=0$. See on alternatiivne lahendus a)-osale.

\emph{Märkus 2.} Arvestades, et karakteristliku polünoomi juured on maatriksi omaväärtused, on $q$ juured parajasti $A$ omaväärtused.

Kui polünoomidel $p$ ja $q$ ei ole ühiseid juuri, siis polünoomi $p=(X-d_1)\cdots(X-d_m)$ mistahes juure $d_j$ korral $\det(A-d_jI)\ne0$. Et $p(A)=\prod_{j=1}^m(A-d_jI)$, siis saame, et $\det(p(A))=\prod_{j=1}^m\det(A-d_j I)\ne0$ ehk maatriks $p(A)$ on pööratav. Vastupidi, kui $\det(p(A))\ne0$, siis pole ükski kompleksarvudest $d_j$ maatriksi $A$ omaväärtus ehk ei ole polünoomi $q$ juur, mistõttu polünoomidel $p$ ja $q$ puuduvad ühised juured.

\emph{Märkus 3 (Urmas Luhaäär).} Piisavuse osa saab tõestada ka järgnevalt.
Kui $p(A)$ on mittepööratav, leidub selline nullist erinev $x$, et $p(A)x=0$. Tähistame $p(A)=\prod_{j=1}^m(A-d_jI)$; esiteks on võimalik, et $Ax - d_mx = 0$, sel juhul on $d_m$ ühtlasi $A$ omaväärtus ehk $q$ juur. Kui $Ax-d_m x \ne0$, tähistame $x_1 = Ax-d_m x$ ning uurime vektorit
$\prod_{j=1}{m-1}(A-d_j I ) x_1$. Juhul, kui $Ax_1-d_{m-1} x_1=0$, on $d_{j-1}$ maatriksi $A$ omaväärtus ehk $q$ juur. Kui aga $Ax_1-d_{m-1} x_1\ne0$, tähistame ta sümboliga $x_2$ ja jätkame analoogselt. Kõige halvemal juhul jõuame olukorrani, kus $A x_{m-1} - d_1 x_{m-1}=0$ (eelnevad sellised vektorid $x_1,x_2,\ldots,x_{m-1}$ olid nullist erinevad); nüüd on $d_1$ maatriksi $A$ omaväärtus ehk $q$ juur. Seega igal juhul on polünoomidel $p$ ja $q$ ühine juur.
\end{enumerate}
\end{document}
