\[\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bff}{\mathbf{f}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bi}{\mathbf{i}}
\newcommand{\bj}{\mathbf{j}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\bN}{\mathbf{N}}
\newcommand{\bn}{\mathbf{n}}
\newcommand{\bo}{\mathbf{0}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\nv}{\mathbf{0}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\rA}{\mathrm{A}}
\newcommand{\rB}{\mathrm{B}}
\newcommand{\rC}{\mathrm{C}}
\newcommand{\rD}{\mathrm{D}}
\newcommand{\rE}{\mathrm{E}}
\newcommand{\rF}{\mathrm{F}}
\newcommand{\rG}{\mathrm{G}}
\newcommand{\rH}{\mathrm{H}}
\newcommand{\rI}{\mathrm{I}}
\newcommand{\rJ}{\mathrm{J}}
\newcommand{\rK}{\mathrm{K}}
\newcommand{\rL}{\mathrm{L}}
\newcommand{\rM}{\mathrm{M}}
\newcommand{\rN}{\mathrm{N}}
\newcommand{\rO}{\mathrm{O}}
\newcommand{\rP}{\mathrm{P}}
\newcommand{\rQ}{\mathrm{Q}}
\newcommand{\rR}{\mathrm{R}}
\newcommand{\rS}{\mathrm{S}}
\newcommand{\rT}{\mathrm{T}}
\newcommand{\rU}{\mathrm{U}}
\newcommand{\rV}{\mathrm{V}}
\newcommand{\rW}{\mathrm{W}}
\newcommand{\rX}{\mathrm{X}}
\newcommand{\rY}{\mathrm{Y}}
\newcommand{\rZ}{\mathrm{Z}}
\newcommand{\pv}{\overline}
\newcommand{\iu}{\mathrm{i}}
\newcommand{\ju}{\mathrm{j}}
\newcommand{\im}{\mathrm{i}}
\newcommand{\e}{\mathrm{e}}
\newcommand{\real}{\operatorname{Re}}
\newcommand{\imag}{\operatorname{Im}}
\newcommand{\Arg}{\operatorname{Arg}}
\newcommand{\Ln}{\operatorname{Ln}}
\DeclareMathOperator*{\res}{res}
\newcommand{\re}{\operatorname{Re}}
\newcommand{\im}{\operatorname{Im}}
\newcommand{\arsinh}{\operatorname{ar\,sinh}}
\newcommand{\arcosh}{\operatorname{ar\,cosh}}
\newcommand{\artanh}{\operatorname{ar\,tanh}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\rref}{\operatorname{rref}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\Span}{\operatorname{span}}
\newcommand{\vir}{\operatorname{span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\alg}{\operatorname{alg}}
\newcommand{\geom}{\operatorname{geom}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\tp}[1]{#1^{\top}}
\renewcommand{\d}{\mathrm{d}}
\newcommand{\sij}[2]{\bigg/_{\mspace{-15mu}#1}^{\,#2}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\pysty}[1]{\left[\begin{array}{@{}r@{}}#1\end{array}\right]}
\newcommand{\piste}{\cdot}
\newcommand{\qedhere}{}
\newcommand{\taumatrix}[1]{\left[\!\!#1\!\!\right]}
\newenvironment{augmatrix}[1]{\left[\begin{array}{#1}}{\end{array}\right]}
\newenvironment{vaugmatrix}[1]{\left|\begin{array}{#1}}{\end{array}\right|}
\newcommand{\trans}{\mathrm{T}}
\newcommand{\EUR}{\text{\unicode{0x20AC}}}
\newcommand{\SI}[3][]{#2\,\mathrm{#3}}
\newcommand{\si}[2][]{\mathrm{#2}}
\newcommand{\num}[2][]{#2}
\newcommand{\ang}[2][]{#2^{\circ}}
\newcommand{\meter}{m}
\newcommand{\metre}{\meter}
\newcommand{\kilo}{k}
\newcommand{\kilogram}{kg}
\newcommand{\gram}{g}
\newcommand{\squared}{^2}
\newcommand{\cubed}{^3}
\newcommand{\minute}{min}
\newcommand{\hour}{h}
\newcommand{\second}{s}
\newcommand{\degreeCelsius}{^{\circ}C}
\newcommand{\per}{/}
\newcommand{\centi}{c}
\newcommand{\milli}{m}
\newcommand{\deci}{d}
\newcommand{\percent}{\%}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Corr}{\operatorname{Corr}}
\newcommand{\Tasd}{\operatorname{Tasd}}
\newcommand{\Ber}{\operatorname{Ber}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\Geom}{\operatorname{Geom}}
\newcommand{\Poi}{\operatorname{Poi}}
\newcommand{\Hyperg}{\operatorname{Hyperg}}
\newcommand{\Tas}{\operatorname{Tas}}
\newcommand{\Exp}{\operatorname{Exp}}
\newcommand{\tdist}{\operatorname{t}}
\newcommand{\rd}{\mathrm{d}}\]
\({}^*\)Differenssiyhtälöt
Rekursio on eräs matematiikassa yleinen tapa määritellä lukujonoja. Rekursion ideana on määrittää lukujonon \(n\):s termi aiempien termien avulla antamalla tälle jokin sääntö. Määrittelyä käytettiin jo aiemmin esimerkin 5.2.3 kohdissa 2 ja 3, joissa määriteltiin sääntö ja annettiin riittävä määrä lukujonon alkutermejä, jotta rekursio on hyvin määritelty.
Rekursiota voidaan tarkastella myös analogisesti lineaaristen differentiaaliyhtälöiden kanssa. Tarkastellaan 2. kertaluvun lineaarista vakiokertoimista differenssiyhtälöä
(1)\[a_n+ba_{n-1}+ca_{n-2}=f(n),\]
missä \(b,c\in\mathbb{R}\) ja \(f:\mathbb{N}\cup\{0\}\to\mathbb{R}\) on jokin annettu funktio. Oletetaan lisäksi, että differenssiyhtälölle on annettu alkuehdot \(a_0=A_0\) ja \(a_1=A_1\). Näin saadun differenssiyhtälön alkuarvo-ongelman ratkaisu etenee täysin analogisesti 2. kertaluvun lineaarisen vakiokertoimisen differentiaaliyhtälön alkuarvo-ongelman ratkaisemisen kanssa, joten rajoitutaan tässä kappaleessa vain ratkaisun periaatteeseen.
Jos \(f(n)=0\) jokaisella \(n\), kutsutaan differenssiyhtälöä (1) homogeeniseksi, muulloin epähomogeeniseksi.
Homogeenisen yhtälön yleisen ratkaisun
\[a_n=C_1a_n^{(1)}+C_2a_n^{(2)}\]
löytämiseksi tarvitaan kaksi lineaarisesti riippumatonta ratkaisua \(a_n^{(1)}\) ja \(a_n^{(2)}\).
Lause 5.6.2
Jos karakteristisella yhtälöllä on
kaksi erillistä reaalista juurta \(r_1\) ja \(r_2\), niin alkuperäisen yhtälön yleinen ratkaisu on
\[a_n=C_1r_1^n+C_2r_2^n,\]
reaalinen kaksoisjuuri \(r_0\), niin alkuperäisen yhtälön yleinen ratkaisu on
\[a_n=C_1r_0^n+C_2nr_0^n,\]
imaginaariset juuret \(r_{\pm}=\alpha\pm\beta i\), niin alkuperäisen yhtälön
yleinen ratkaisu on
\[a_n=\rho^n\big(C_1\sin(\theta n)+C_2\cos(\theta n)\big),\]
missä \(\rho=|r_+|\) ja \(\theta=\text{Arg}(r_+)\), eli Eulerin kaavan avulla \(r_+=\rho e^{i\theta}\).
Piilota/näytä todistus
Sijoittamalla differenssiyhtälöön yrite
\(a_n=r^n\) on todistus analoginen
lauseen 4.2.14 todistuksen kanssa ja jätetään asiasta kiinnostuneen lukijan täydennettäväksi.
Esimerkki 5.6.3
Etsi homogeenisen differenssiyhtälön
\[a_{n}-3a_{n-1}+2a_{n-2}=0\]
yleinen ratkaisu.
Piilota/näytä ratkaisu
Yhtälön karakteristinen yhtälö on
\[r^2-5r+6=0,\]
jolla reaaliset juuret \(r_1=2\) ja \(r_2=3\). Edellisen lauseen mukaan yleinen ratkaisu on tällöin muotoa
\[a_n=C_12^n+C_23^n.\qedhere\]
Epähomogeenisen yhtälön yleinen ratkaisu löydetään vastaavasti.
Lause 5.6.4
Jos \(a_n^h=C_1a_n^{(1)}+C_2a_n^{(2)}\) on homogeenisen yhtälön yleinen ratkaisu ja \(a_n^p\) on epähomogeenisen yhtälön yksittäisratkaisu, niin epähomogeenisen yhtälön yleinen ratkaisu on
\[a_n=a_n^h+a_n^p=C_1a_n^{(1)}+C_2a_n^{(2)}+a_n^p.\]
Epähomogeeniyhtälön yksittäisratkaisun löytäminen menee analogisesti määräämättömien kertoimien menetelmän kanssa.
Esimerkki 5.6.5
Etsi differenssiyhtälön
\[a_{n}-3a_{n-1}+2a_{n-2}=4^n\]
yleinen ratkaisu ja alkuehdot \(a_0=0\), \(a_1=1\) toteuttava ratkaisu.
Piilota/näytä ratkaisu
Homogeenisen yhtälön yleinen ratkaisu laskettiin edellisessä esimerkissä. Etsitään epähomogeenisen yhtälön yleistä ratkaisua sijoittamalla yrite \(a_n=D4^n\), jolloin
\[\begin{split}\begin{aligned}
a_{n}-3a_{n-1}+2a_{n-2}&=D4^n-D3\cdot 4^{n-1}+D2\cdot 4^{n-2}\\
&=D4^n-D3\cdot \frac{4}{4}\cdot 4^{n-1}+D2\cdot \frac{4^2}{4^2}\cdot 4^{n-2}\\
&=D4^n-D \frac{3}{4}\cdot 4^{n}+D \frac{2}{4^2}\cdot 4^{n}\\
&=D\Big(1-\frac{3}{4}+\frac{1}{8}\Big) 4^{n}\\
&=D\frac{3}{8} 4^{n}.
\end{aligned}\end{split}\]
Kun valitaan \(D=\frac{8}{3}\), saadaan homogeenisen yhtälön yksityisratkaisuksi \(a_n^p=\frac{8}{3}4^n\) ja yleiseksi ratkaisuksi
\[a_n=C_12^n+C_23^n+\frac{8}{3}4^n.\]
Yhtälöparista
\[\begin{split}\begin{aligned}
a_0&=C_1+C_2+\frac{8}{3}=0,\\
a_1&=C_12+C_23+\frac{8}{3}4=1
\end{aligned}\end{split}\]
saadaan ratkaisuina \(C_1=\frac{5}{3}\) sekä \(C_2=-\frac{13}{3}\) ja näin alkuarvo-ongelman ratkaisuksi tulee
\[a_n=\frac{5}{3}2^n-\frac{13}{3}3^n+\frac{8}{3}4^n.\qedhere\]