\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,vollstaendige-induktion}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Methode „sumOfSquares()“},
  Referenz = 66115-2017-F.T1-A4,
  RelativerPfad = Examen/66115/2017/03/Thema-1/Aufgabe-4.tex,
  ZitatSchluessel = sosy:ab:8,
  ZitatBeschreibung = {Aufgabe 4},
  BearbeitungsStand = mit Lösung,
  Korrektheit = korrekt und überprüft,
  Ueberprueft = {Mit Dozentenlösung abgeglichen},
  Stichwoerter = {Vollständige Induktion},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 4,
}

\let\m=\bInduktionMarkierung
\let\e=\bInduktionErklaerung

Sie\index{Vollständige Induktion} \footcite[Aufgabe 4]{sosy:ab:8} dürfen im
Folgenden davon ausgehen, dass keinerlei Under- oder Overflows
auftreten.
\footcite{examen:66115:2017:03}

\bigskip

\noindent
Gegeben sei folgende rekursive Methode für $n \geq 0$:

\begin{bJavaAngabe}
long sumOfSquares (long n) {
  if (n == 0)
    return 0;
  else
    return n * n + sumOfSquares(n - 1);
}
\end{bJavaAngabe}

\begin{enumerate}

%%
% (a)
%%

\item Beweisen Sie formal mittels vollständiger Induktion:

\begin{displaymath}
\forall n \in \mathbb{N} : \texttt{sumOfSquares(n)} =
\frac{n(n + 1)(2n + 1)}{6}
\end{displaymath}

\begin{bAntwort}
Sei $f(n): \frac{n(n + 1)(2n + 1)}{6}$

%%
%
%%

\bInduktionAnfang

Für $n = 0$ gilt:

$\texttt{sumOfSquares(0)} \overset{\texttt{if}}{=} 0 = f(0)$

%%
%
%%

\bInduktionVoraussetzung

Für ein festes $n \in \mathbb{N}$ gelte:

$\texttt{sumOfSquares(n)} = f(n)$

%%
%
%%

\bInduktionSchritt

$n \rightarrow n + 1$

\begin{align*}
f(n + 1)
& = \texttt{sumOfSquares(n+1)}
& \e{Java-Methode eingesetzt}\\
%
& \overset{\texttt{else}}{=} \texttt{(n+1)*(n+1) + sumOfSquares(n)}
& \e{Java-Code der else-Verzweigung verwendet}\\
%
& \overset{\texttt{I.H.}}{=} (n + 1) (n + 1) + f(n)
& \e{mathematisch notiert}\\
%
& = (n + 1) (n + 1) + \m{\frac{n(n + 1)(2n + 1)}{6}}
& \e{Formel eingesetzt}\\
%
& = \m{(n + 1)^2} + \frac{n(n + 1)(2n + 1)}{6}
& \e{potenziert}\\
%
& = \frac{\m{6}(n + 1)^2}{\m{6}} + \frac{n(n + 1)(2n + 1)}{6}
& \e{$(n + 1)^2$ in Bruch umgewandelt}\\
%
& = \frac{6(n + 1)^2 + n(n + 1)(2n + 1)}{\m{6}}
& \e{Addition gleichnamiger Brüche}\\
%
& = \frac{\m{(n + 1)} 6 (n + 1) + \m{(n + 1)}n(2n + 1)}{\m{6}}
& \e{$n + 1$ ausklammern vorbereitet}\\
%
%
& = \frac{\m{(n + 1)(}6(n + 1) + n(2n + 1)\m{)}}{6}
& \e{$n + 1$ ausgeklammert}\\
%
& = \frac{(n + 1)(\m{6n + 6 + 2n^2 + n}))}{6}
& \e{Klammern ausmultipliziert / aufgelöst}\\
%
& = \frac{(n + 1)(2n^2 + \m{7n} + 6)}{6}
& \e{umsortiert, addiert $6n + n = 7n$}\\
%
& = \frac{(n + 1)(2n^2 + \m{3n + 4n} + 6)}{6}
& \e{Ausklammern vorbereitet}\\
%
& = \frac{(n + 1)\m{(n + 2)} (2n + 3)}{6}
& \e{$(n + 2)$ ausgeklammert}\\
%
& = \frac{\m{(n + 1)}(\m{(n + 1)} + 1) (2\m{(n + 1)} + 1))}{6}
& \e{$(n + 1)$ verdeutlicht}\\
\end{align*}
\bFussnoteUrl{https://mathcs.org/analysis/reals/infinity/answers/sm_sq_cb.html}
\end{bAntwort}

%%
% (b)
%%

\item Beweisen Sie die Terminierung von \bJavaCode{sumOfSquares(n)} für alle
$n \geq 0$.

\begin{bAntwort}
Sei $T (n) = n$. Die Funktion $T (n)$ ist offenbar ganzzahlig. In jedem
Rekursionsschritt wird $n$ um eins verringert, somit ist $T (n)$ streng
monoton fallend. Durch die Abbruchbedingung \bJavaCode{n==0} ist $T (n)$
insbesondere nach unten beschränkt. Somit ist $T$ eine gültige
Terminierungsfunktion.
\end{bAntwort}

\end{enumerate}
\end{document}