\section{Einstimmung}\label{Grund}


\subsection{Vollst"andige Induktion und binomische Formel}\label{Ein}
\begin{Satz}\label{ErF} F"ur jede nat"urliche Zahl $n\geq 1$ gilt
$1+2+\ldots +n = \frac{n(n+1)}{2}$.
\end{Satz}
\begin{Beispiel}
Im Fall $n=5$ behauptet unser Satz  $1+2+3+4+5=5\times 6/2$ und in
diesem Fall stimmt das schon mal: Beide Seiten sind $15$. 
Man bemerke, da"s wir beim Rechnen mit Symbolen wie
etwa $ n(n+1)$
die Multiplikationssymbole weggelassen haben, die nur beim Rechnen mit
durch Ziffern dargestellten Zahlen  wichtig sind. 
\end{Beispiel}
\begin{proof}[Beweis]
Bei diesem Beweis sollen Sie gleichzeitig das 
Beweisprinzip der {\bf voll\-st"andigen
Induktion}\index{Induktion, vollst"andige} lernen.
Wir bezeichnen mit $A(n)$ die Aussage, da"s die Formel im Satz 
f"ur ein gegebenes $n$ gilt, und zeigen:
\begin{description}
\item[Induktionsbasis:]\index{Induktion, vollst"andige!Induktionsbasis}
Die Aussage $A(1)$ ist richtig. In der Tat gilt 
 $1= \frac{1(1+1)}{2}$.
\item[Induktionsschritt:]\index{Induktion, vollst"andige!Induktionsschritt}
Aus der Aussage 
$A(n)$ folgt die Aussage 
$A(n+1)$. In der Tat, unter der Annahme, da"s unsere Formel
f"ur ein gegebenes $n$ gilt, der sogenannten 
{\bf Induktionsannahme}\index{Induktion, vollst"andige!Induktionsannahme} oder
{\bf Induktionsvoraussetzung}\index{Induktion, vollst"andige!Induktionsvoraussetzung}, 
rechnen wir
$$\begin{array}{rcl}
1+2+\ldots + n + (n+1) &= &\frac{n(n+1)}{2} + \frac{2(n+1)}{2}\\[2mm]
&=& \frac{(n+2)(n+1)}{2}\\[2mm]
&=& \frac{(n+1)((n+1)+1)}{2}
\end{array}$$
und folgern so, da"s die Formel auch f"ur $n+1$ gilt.
\end{description}
Es ist damit klar, da"s unsere Aussage
$A(n)$ richtig ist alias da"s unsere Formel  
gilt f"ur alle $n = 1,2,3,$ \dots
\end{proof}
\begin{Bemerkungl}
  Das Zeichen $\qedsymbol$\index{)0a@$\qedsymbol$ Beweisende}  
 deutet in diesem Text  das Ende eines Beweises an
und ist in der neueren Literatur weit verbreitet. 
Buchstaben in Formeln
 werden in der
Mathematik "ublicherweise kursiv notiert, so wie etwa 
das $n$ oder auch das $A$ im
vorhergehenden Beweis. Nur Buchstaben oder Buchstabenkombinationen,
die stets dasselbe bedeuten sollen, schreibt man nicht kursiv,
wie etwa $\op{sin}$ f"ur den Sinus oder $\op{log}$
f"ur den Logarithmus. 
\end{Bemerkungl}
\begin{Bemerkungl}
Der vorhergehende
Beweis st"utzt sich auf unser intuitives Verst"andnis der nat"urlichen
Zahlen.
Man kann das Konzept der nat"urlichen Zahlen auch formal einf"uhren
und so die nat"urlichen Zahlen in gewisser Weise \glqq besser\grqq\  verstehen. 
Das wird in \eref{DNZZ}{GR} und ausf"uhrlicher in 
\eref{Nhoc}{LA1} diskutiert. 
Das Wort \glqq Induktion\grqq\  meint eigentlich \glqq Hervorrufen\grqq,
so wie etwa das Betrachten einer Wurst die Aussch"uttung von Spucke induziert 
alias uns den Mund w"assrig macht. Im Zusammenhang der 
vollst"andigen Induktion ist es dahingehend zu verstehen, da"s die
Richtigkeit unserer Aussage $A(1)$ die Richtigkeit von $A(2)$ 
induziert, die Richtigkeit von $A(2)$ hinwiederum die Richtigkeit 
von $A(3)$, die Richtigkeit von $A(3)$  die Richtigkeit 
von $A(4)$, und immer so weiter. 
\end{Bemerkungl}

\begin{Bemerkungl}
Es herrscht keine Einigkeit in der Frage, ob 
man die Null eine nat"urliche Zahl nennen soll. In diesem Text
ist stets die Null mit gemeint, wenn von nat"urlichen
Zahlen die Rede ist. Wollen wir die Null dennoch ausschlie"sen, 
so sprechen wir wie oben von einer
  \glqq nat"urlichen Zahl $n\geq 1$\grqq.
\end{Bemerkungl}
  

\begin{Bemerkungl}
  Ich will kurz begr"unden, warum es mir nat"urlich scheint, auch die Null 
eine nat"urliche Zahl zu nennen:
  Hat bildlich gesprochen jedes Kind einer Klasse einen Korb mit "Apfeln vor
  sich und soll seine "Apfel z"ahlen, so kann es ja 
durchaus vorkommen, da"s in
  seinem Korb gar kein Apfel liegt, weil es zum Beispiel alle seine "Apfel
  bereits gegessen hat.  In der Begrifflichkeit der Mengenlehre ausgedr"uckt,
  die wir in \eref{Meng}{GR} einf"uhren werden, mu"s man die leere Menge endlich
  nennen, wenn man erreichen will, da"s 
jede Teilmenge einer endlichen Menge wieder endlich ist.  Will
  man dann zus"atzlich 
erreichen, da"s die Kardinalit"at jeder endlichen Menge eine
  nat"urliche Zahl ist, so darf man die Null nicht aus den nat"urlichen Zahlen
  herauslassen.
\end{Bemerkungl}
\begin{figure}[htbp]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bild0003}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Die Gesamtfl"ache dieses Treppenquerschnitts ist offensichtlich
$$4^2/2+4/2=4\cdot 5/2=10$$
\end{minipage}
\end{figure}

\begin{Bemerkungl}\label{SSF}
Man kann sich den Satz anschaulich, wie in nebenstehendem Bild angedeutet,  
klar machen als eine Formel f"ur die Fl"ache des Querschnitts
durch eine Treppe der L"ange $n$ mit Stufenabstand und Stufenh"ohe Eins.
In der Tat bedeckt 
ein derartiger Querschnitt 
ja offensichtlich ein halbes Quadrat der Kantenl"ange $n$ nebst
$n$ halben Quadraten der Kantenl"ange Eins.
Ein weiterer Beweis geht so:
$$\begin{array}{rcrlccc}
1 + 2 + 3+\ldots +n&=&1/2 &+ \;\;\;\; 2/2 &+\;\;\;\; 3/2 &+ \ldots &+\; n/2 \\
&&+ \; n/2 &+ (n-1)/2& + (n-2)/2& + \ldots &+\; 1/2\\[2mm]
&=& \frac{n+1}{2} &+ \;\;\;\; \frac{n+1}{2}&+ \;\;\;\; \frac{n+1}{2}& + \ldots &+\; \frac{n+1}{2}\\[2mm]
& = & n(n+1)/2 \hspace{-1cm}&& &  &
\end{array}$$
Ich will letzteren Beweis benutzen, um eine neue Notation einzuf"uhren.
\end{Bemerkungl}
\begin{Definition}
Gegeben $a_{1},a_{2},\ldots , a_{n}$ schreiben wir
$$\sum^{n}_{i=1} a_{i} \pdef a_{1}+a_{2}+ \ldots + a_{n}$$
Das Symbol $\sum$ ist ein gro"ses griechisches S und steht f"ur \glqq Summe\grqq.
Das Symbol 
$\pdef$\index{)8@$\pdef$ ist definiert durch}\index{)8@$\defp$ wird definiert als} 
deutet an, da"s die Bedeutung der\label{Summ}  
Symbole auf der doppelpunktbehafteten  Seite des Gleichheitszeichens
 durch den Ausdruck auf der  anderen Seite unseres Gleichheitszeichens
definiert ist.
Im obigen und "ahnlichen\index{S@$\sum$ Summe!von Zahlen}\index{)9@$\sum$ Summe!von Zahlen}
Zusammenh"angen hei"sen
$a_1,\ldots, a_n$   die \defind{Summanden} und $i$  der
\defind{Laufindex}, da er eben etwa in unserem Fall von $1$ bis $n$
l"auft und anzeigt alias \glqq indiziert\grqq, welcher Summand gemeint ist. 
\end{Definition}
\begin{Bemerkungl}[\textbf{Zur Sprache in der Mathematik}]
Das Wort \glqq Definition\grqq\   kommt\index{Definition}  aus dem
Lateinischen und bedeutet  \glqq Abgrenzung\grqq. In 
Definitionen versuchen wir, die Bedeutung von  Symbolen und Begriffen
so klar wie m"oglich festzulegen. Sie werden merken, da"s 
man in der Mathematik die Angwohnheit hat, in Definitionen
Worte der Umgangssprache wie Menge, Gruppe, K"orper,
Unterk"orper, Abbildung etcetera \glqq umzuwidmen\grqq\  und ihnen ganz spezielle und
meist nur noch entfernt mit der umgangssprachlichen Bedeutung verwandte
neue Bedeutungen zu geben. In mathematischen Texten sind dann 
"uberwiegend diese umgewidmeten Bedeutungen gemeint. In dieser Weise
baut die Mathematik also wirklich ihre eigene Sprache auf, bei der
jedoch die Grammatik und auch nicht ganz wenige W"orter 
doch wieder von den uns gel"aufigen
Sprachen "ubernommen werden. 
Das mu"s insbesondere f"ur den Anf"anger verwirrend sein, der sich auch
bei ganz harmlos daherkommenden W"ortern stets wird fragen 
m"ussen, ob sie denn nun 
umgangssprachlich gemeint sind oder vielmehr bereits durch eine 
Definition auf eine mehr oder weniger andere
und viel genauere Bedeutung festgelegt wurden.
Um hier zu helfen, habe ich mir
gro"se M"uhe mit dem Index gegeben, den Sie ganz am Schlu"s dieses Skriptums
finden
und in dem alle  
an verschiedenen Stellen eingef"uhrten oder umgewidmeten 
und dort fett gedruckten 
Begriffe verzeichnet sein sollten.
Und an dieser Stelle  mu"s ich Sie schon bitten, das Wort \glqq Index\grqq\ 
 nicht als Laufindex mi"szuverstehen!
\end{Bemerkungl}
\begin{Beispiel}
In der $\sum$-Notation liest sich der in \ref{SSF} gegebene Beweis so:
$$\begin{array}{lcl}
\sum^{n}_{i=1} i
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{i=1} \frac{i}{2}\\[2mm]
&&\text{und nach Indexwechsel $i=n+1-k$ hinten}\\
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{k=1} \frac{n+1-k}{2}\\[2mm]
&&\text{dann mache  $k$ zu $i$ in der zweiten Summe}\\
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{i=1} \frac{n+1-i}{2}\\[2mm]
&&\text{und nach  Zusammenfassen beider Summen}\\
& =& \sum^{n}_{i=1} \frac{n+1}{2}\\[2mm]
&&\text{ergibt sich offensichtlich}\\
&=& n(\frac{n+1}{2})
\end{array}$$  
 \end{Beispiel}

 \begin{Beispiel}
 Einen anderen Beweis derselben Formel liefert
die  Gleichungskette:
$$(n+1)^2=\sum_{i=0}^{n}(i+1)^2-i^2=\sum_{i=0}^{n}2i +1
=2\sum_{i=0}^{n}i +\sum_{i=0}^{n}1=n+1+2\sum_{i=0}^{n}i $$
 \end{Beispiel}
\begin{Definition}
  In einer "ahnlichen Bedeutung wie das Symbol
  $\sum$ verwendet man auch 
das Symbol $\prod$,\index{P@$\prod$ Produkt!von Zahlen} ein gro"ses\index{)9@$\prod$ Produkt!von Zahlen}
griechisches $P$, f"ur \glqq Produkt\grqq\  und
schreibt $$\prod^{n}_{i=1} a_{i}\pdef a_{1}a_{2}\ldots a_{n}$$  
Die  $a_1,\ldots, a_n$ hei"sen in diesem und "ahnlichen
Zusammenh"angen die \defind{Faktoren} des Produkts.
\end{Definition}


\begin{Definition}
F"ur jede nat"urliche Zahl $n\geq 1$ definieren wir die Zahl
$n!$ (sprich: $n$ {\bf Fakult"at})\index{Fakult"at}  
\index{)0b@$n~!$ Fakult"at} durch 
die Formel
$$n! \pdef 1\cdot 2 \cdot\ldots \cdot n  = \prod^{n}_{i=1} i$$
Wir treffen zus"atzlich
die Vereinbarung
$0! \pdef 1$ und haben also 
$0! =1$, $1!=1$, $2!=2$, $3! = 6$, $4!=24$ und so weiter.
\end{Definition}
\begin{Bemerkungl}[\textbf{Allgemeinere Summen und Produkte}] 
Wir vereinbaren, da"s Produkten,\label{LPS} 
bei denen die obere Grenze des Laufindex 
um Eins kleiner ist als seine untere Grenze, 
der Wert $1$ zugewiesen werden soll,
also etwa  $1=\prod^{0}_{i=1} i=0!$.
Ebenso vereinbaren wir auch, da"s 
Summen, bei denen die obere Grenze des Laufindex 
um Eins kleiner ist als seine untere Grenze, 
der Wert $0$ zugewiesen werden soll, so da"s wir in Erweiterung unserer Formel
\ref{ErF} etwa schreiben k"onnten
$0=\sum^{0}_{i=1} i$. Der Sinn dieser Erweiterungen zeigt sich darin,
da"s damit Formeln wie $\sum_{i=k}^la_i=\sum_{i=k}^ma_i+\sum_{i=m+1}^la_i$
auch f"ur $m=k-1$ richtig bleiben. Man mag sogar noch weiter gehen 
und die Definition von Summen und Produkten
auf beliebige untere und obere Grenzen
so erweitern, da"s  diese Formeln richtig bleiben, zumindest wenn alle
Summanden ein Negatives beziehungsweise alle Faktoren einen Kehrwert haben. In dieser Allgemeinheit
ist die fragliche Notation jedoch nur beim kontinuierlichen Analogon
$\int$ des Summenzeichens "ublich, wie in \eref{IGV}{AN1} ausgef"uhrt
werden wird.
\end{Bemerkungl}
\begin{Satz}[\textbf{Bedeutung der Fakult"at}]\label{BFa}
Es gibt
genau 
$n!$  M"oglichkeiten, $n$  
voneinander verschiedene Objekte in eine Reihenfolge zu
bringen.  
\end{Satz}
\begin{Beispiel}
Es gibt genau $3! = 6$ M"oglichkeiten, die drei
Buchstaben $a,b$ und $c$ in eine Reihenfolge zu bringen, n"amlich
$$\begin{array}{ccc}
abc & bac & cab \\
acb & bca & cba
\end{array}$$  In gewisser Weise stimmt unser Satz sogar f"ur $n=0$:
In der Terminologie, die wir in \eref{OM}{AN1} einf"uhren, gibt es 
 genau
eine Anordnung der leeren Menge.  
\end{Beispiel}
\begin{proof}
Hat man  $n$ voneinander verschiedene Objekte, so hat man $n$ M"oglichkeiten,
ein Erstes auszusuchen, dann $(n-1)$ M"oglichkeiten, ein Zweites
auszusuchen und so weiter, bis schlie"slich nur noch eine
M"oglichkeit bleibt, ein Letztes auszusuchen.
Insgesamt haben wir also wie behauptet $n!$ m"ogliche
Reihenfolgen. 
\end{proof}
\begin{Definition}\label{BiKoe}
Wir definieren  f"ur beliebiges $n$ und jede nat"urliche Zahl $k$
den {\bf Binomialkoeffizienten}\index{Binomialkoeffizienten} ${n \choose k}$
(sprich: $n$ {\bf "uber} $k$)\index{)5)@${n \choose k}$ Binomialkoeffizient}
 durch die Regeln
$${n \choose k} \pdef \prod^{k-1}_{j=0} \frac{n-j}{k-j} =
\begin{array}{rc}
n (n-1) \ldots &(n-k+1)\\
\hline
k(k-1)\ldots& 1\end{array}\;
\text{ f"ur $k\geq 1$ und } {n \choose 0}\pdef 1.$$  
Der Sonderfall $k=0$ wird im "Ubrigen auch durch unsere 
allgemeine Formel gedeckt, wenn wir unsere Konvention \ref{LPS} 
beherzigen.
Im Lichte des folgenden Satzes schlage ich vor, die Binomialkoeffizienten
${n\choose k}$ statt \glqq $n$ "uber $k$\grqq\  inhaltsreicher \glqq $k$ aus $n$\grqq\ 
zu sprechen.
\end{Definition}
\begin{Bemerkungl}
  Die  Bezeichnung als Binomialkoeffizienten
leitet sich von dem Auftreten 
dieser Zahlen als Koeffizienten in der
 \glqq binomischen Formel\grqq\  \ref{BiFoA} ab.
\end{Bemerkungl}

\begin{Satz}[\textbf{Bedeutung der Binomialkoeffizienten}]
Gegeben  na\-t"urliche Zahlen\label{BBK} $n$ und $k$ 
gibt es genau ${n \choose k}$ M"oglichkeiten, aus 
$n$ voneinander verschiedenen Objekten  $k$ Objekte  auszuw"ahlen.
\end{Satz}
\begin{Beispiel}
Es gibt genau ${4 \choose 2} = \frac{4\cdot 3}{2\cdot 1} =6 $
M"oglichkeiten, aus den vier Buchstaben $a,b,c,d$ zwei auszuw"ahlen,
n"amlich
$$\begin{array}{lll}
a,b \;& b,c \;& c,d \\
a,c & b,d &  \\
a,d & &
\end{array}$$
\end{Beispiel}


\begin{proof}[Beweis]
Wir haben $n$ M"oglichkeiten, ein erstes Objekt auszuw"ahlen, dann
$n-1$ M"oglichkeiten, ein zweites Objekt auszuw"ahlen, und so weiter, 
also insgesamt $n(n-1)
\ldots (n-k+1)$ M"oglichkeiten, $k$ Objekte {\em der Reihe nach}
auszuw"ahlen. Auf die Reihenfolge, in der wir
ausgew"ahlt haben, kommt es uns aber gar nicht an, 
jeweils genau $k!$ von
unseren $n(n-1) \ldots (n-k+1)$ M"oglichkeiten f"uhren 
nach \ref{BFa}  also zur Auswahl
derselben $k$ Objekte.
Man bemerke, da"s unser Satz auch im Extremfall $k=0$ noch stimmt, wenn wir
ihn geeignet interpretieren: In der Terminologie, die wir gleich einf"uhren
werden, besitzt in der Tat jede Menge genau eine
nullelementige Teilmenge, n"amlich die leere Menge. 
\end{proof} 
\begin{Bemerkungl}
Offensichtlich gilt f"ur alle nat"urlichen 
Zahlen $n$ mit $n\geq k$ die Formel
$${n\choose k} = \frac{n!}{k!(n-k)!} = {n\choose n-k}$$
Das folgt einerseits sofort aus der formalen Definition
und ist andererseits auch klar nach der oben erkl"arten Bedeutung der
Binomialkoeffizienten: Wenn wir aus $n$ Objekten $k$ Objekte 
ausw"ahlen, so bleiben $n-k$ Objekte "ubrig. Es gibt demnach gleichviele 
M"oglichkeiten, $k$ Objekte 
auszuw"ahlen, wie es M"oglichkeiten gibt, $n-k$ Objekte auszuw"ahlen.
Wir haben weiter ${n\choose n} = {n\choose 0} =1$ f"ur jede 
nat"urliche Zahl $n\geq 0$
sowie
${n \choose 1}= {n\choose n-1} = n$ f"ur jede nat"urliche Zahl $n\geq 1$. 
\end{Bemerkungl}
\begin{Definition}
  Wie in der Schule setzen wir $a^k\pdef\prod_{i=1}^{k} a$\index{)8bb@$a^k$ Potenz} und sprechen diesen
  usdruck \glqq $a$ hoch $k$\grqq. In Worten 
ist also gemeint \glqq das Produkt von $k$-mal dem Faktor $a$\grqq.  
Im Lichte von \ref{LPS} verstehen wir insbesondere $a^0\pdef 1$.  
\end{Definition}

\begin{Satz} F"ur jede nat"urliche Zahl $n$ gilt\label{BiFoA}
die {\bf\em binomische Formel}\index{binomische Formel}
$$(a+b)^{n} = \sum^{n}_{k=0} {n\choose k} a^{k}b^{n-k}$$
\end{Satz}
\begin{Bemerkungl}
Man beachte, wie wichtig unsere Konvention
$a^0=1$ und insbesondere auch ihr Spezialfall $0^0=1$ f"ur die
G"ultigkeit dieser Formel ist. 
\end{Bemerkungl}
\begin{Bemerkungl}
Die Bezeichung 
\glqq binomische Formel\grqq\ 
leitet sich ab von der Vorsilbe \glqq bi\grqq\  f"ur Zwei,
wie etwa in englisch \glqq bicycle\grqq\  f"ur \glqq Zweirad\grqq\  alias \glqq Fahrrad\grqq,
und dem lateinischen Wort 
\glqq nomen\grqq\  f"ur \glqq Namen\grqq. Mit den beiden \glqq Namen\grqq\  sind hier  $a$ und
$b$ gemeint. Mehr dazu wird in \eref{WBPb}{AN1} erkl"art.
\end{Bemerkungl}
\begin{proof}[Erster Beweis]
Beim Ausmultiplizieren
erhalten wir das Monom $a^k b^{n-k}$ so oft, wie es M"oglichkeiten gibt,
aus unseren $n$ Faktoren $(a+b)$ die $k$ Faktoren  auszusuchen,
\glqq in denen wir beim Ausmultiplizieren das $a$ nehmen\grqq. 
Dieses Argument werden wir in \eref{PFB}{GR} 
noch besser formulieren.
\end{proof}
\begin{proof}[Zweiter Beweis]
Dieser Beweis ist eine ausgezeichnete "Ubung im Umgang mit unseren Symbolen
und mit der vollst"andigen Induktion. 
Er scheint mir jedoch auch in einer f"ur Beweise durch 
vollst"andige Induktion typischen Weise wenig durchsichtig.
Zun"achst pr"ufen wir f"ur beliebiges $n$ und jede nat"urliche Zahl
$k\geq 1$ die Formel
$${n\choose k-1} + {n\choose k} = {n+1\choose k}$$
durch explizites Nachrechnen.
Dann geben wir unserer Formel im Satz den Namen $A(n)$ und pr"ufen
die Formel
$A(0)$ und zur Sicherheit auch noch $A(1)$ durch Hinsehen.
Schlie"slich gilt es, den Induktionsschritt durchzuf"uhren,
als da hei"st, $A(n+1)$ aus $A(n)$
zu folgern.
Dazu rechnen wir
$$\begin{array}{ccl}
(a+b)^{n+1} & =& (a+b) (a+b)^{n}\\[2mm]
&&\text{und mit der Induktionsvoraussetzung}\\
& =& (a+b) \sum^{n}_{k=0}{n\choose k} a^{k}b^{n-k}\\[2mm]
&&\text{und durch Ausmultiplizieren}\\
&=&\sum^{n}_{k=0}{n\choose k} a^{k+1}b^{n-k}+ \sum^{n}_{k=0} {n\choose k}
a^{k}b^{n-k+1}\\[2mm]
&&\text{und Indexwechsel $k=i-1$ in der ersten Summe}\\
&=&\sum^{n+1}_{i=1} {n\choose i-1}a^{i}b^{n-i+1}+ \sum^{n}_{k=0}
{n\choose k} a^{k}b^{n-k+1}\\[2mm]
&&\text{dann mit  $k$ statt $i$ 
und Absondern von Summanden}\\
&=& a^{n+1}b^{0} + \sum^{n}_{k=1}{n\choose k-1} a^{k}b^{n-k+1} +\\[2mm]
&&\hspace{13mm}+\sum^{n}_{k=1} \;{n\choose k}\; 
a^{k}b^{n-k+1} + a^{0}b^{n+1}\\[2mm]
&&\text{und nach Zusammenfassen der mittleren Summen}\\
&=& a^{n+1}b^{0} + \sum^{n}_{k=1} {n+1\choose k} a^{k}b^{n-k+1}+a^{0}
b^{n+1}\\[2mm]
&&\text{und Einbeziehen der abgesonderten Summanden}\\
&=& \sum^{n+1}_{k=0} {n+1\choose k} a^{k}b^{n+1-k}
\end{array}$$
und folgern so tats"achlich $A(n+1)$ aus $A(n)$.
\end{proof}
\begin{Bemerkungl}
Die Formel ${n\choose k-1} + {n\choose k} = {n+1\choose k}$ f"ur
$k \geq 1$ kann man zur effektiven Berechnung der Binomialkoeffizienten
mit dem sogenannten 
{\bf Pascal'schen Dreieck}\index{Pascal'sches Dreieck} benutzen:
Im Schema
$$\begin{array}{ccccccccc}
 & & & &1& & & &\\
 & & &1& &1& & &\\
 & &1& &2& &1& &\\
 &1& &3& &3& &1& \\
1& &4& &6& &4& &1
\end{array}$$
seien die Einsen an den R"andern vorgegeben und eine Zahl in der Mitte
berechne sich als die Summe ihrer beiden oberen \glqq Nachbarn\grqq. Dann stehen
in der $(n+1)$-ten Zeile der Reihe nach die Binomialkoeffizienten
${n\choose 0}=1, {n\choose 1}=n,  \ldots$, bis 
${n\choose n-1}=n, {n\choose n} =1$. Wir haben also zum Beispiel nach der untersten Zeile in obigem Ausschnitt des Pascal'schen Dreiecks 
$$(a+b)^4=a^4 + 4a^3b + 6 a^2b^2+ 4 ab^3+b^4\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$
\end{Bemerkungl}
\subsubsection*{"Ubungen}
\begin{Ubunge}\label{KBKxx} 
Man zeige:  Ist $p$ eine Primzahl und $n$ nicht durch $p$ teilbar und
$e\geq 0$ eine nat"urliche Zahl, so ist $${p^en \choose p^e}$$ auch nicht
durch $p$ teilbar. Hinweis: Man m"oge bei der L"osung dieser "Ubung
bereits die Erkenntnis verwenden, da"s eine
Primzahl ein Produkt nur teilen kann, wenn sie einen der Faktoren teilt.
Ein Beweis dieser Tatsache wird in \eref{EPf}{LA1} nachgeholt.
\end{Ubunge}
\begin{Ubung}
Man finde und beweise eine Formel f"ur $\sum^n_{i=1}i^2$.
Hinweis: Man suche zun"achst eine Formel f"ur $\sum^n_{i=1}i^3-(i-1)^3$
und beachte $i^3-(i-1)^3=3i^2-3i+1$.
\end{Ubung}

\begin{Ubunge}\label{SNUPO} 
  Man zeige, da"s  f"ur jedes $k\in\DN$ eine Formel der Gestalt
$\sum^n_{i=1}i^k= \frac{1}{k+1}n^{k+1} +a_{k}n^k+\ldots + a_1 n + a_0$ gilt
mit $a_\kappa\in\DQ$.
\end{Ubunge}


\subsection{Fibonacci-Folge und Vektorraumbegriff}\label{FiVe}
\begin{Bemerkungl}
  Ich beginne mit einigen Beispielen f"ur eine mathematische Struktur,
die ihnen im weiteren Verlauf des Studiums  als 
\glqq Vektorraum\grqq\ gel"aufig werden wird.
\end{Bemerkungl}
\begin{Beispiel}\label{FiFo}
Die \defind{Fibonacci-Folge} $$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\ldots $$
entsteht, indem man mit
$f_0=0$ und $f_1=1$ beginnt und dann jedes weitere Folgenglied 
als die
Summe seiner beiden Vorg"anger bildet, in Formeln $$f_{i+2}\pdef f_{i+1}+f_{i}$$ 
Wir
suchen nun f"ur die Glieder $f_i$ dieser Folge eine 
geschlossene Darstellung.
Dazu vereinbaren wir, da"s wir Folgen $x_0, x_1, x_2, \ldots$ mit $x_n =x_{n-1}+x_{n-2}$ f"ur $n = 2,3,4 , \ldots $
 {\bf Folgen vom Fibonacci-Typ}
nennen wollen.
Kennen wir die beiden ersten Glieder 
einer Folge vom Fibonacci-Typ, so legt das nat"urlich bereits die gesamte
Folge fest. 
Nun bemerken wir, da"s f"ur jede Folge 
$x_0,x_1, x_2, \ldots $ vom Fibonacci-Typ
und jedes $\alpha$ auch die Folge
$\alpha x_0, \alpha x_1, \alpha x_2, \ldots$ vom Fibonacci-Typ ist, und da"s
f"ur jede weitere Folge $y_0,y_1,y_2, \ldots $ vom Fibonacci-Typ
auch die gliedweise Summe
$(x_0 + y_0), (x_1 + y_1) , (x_2 + y_2), \ldots $ eine Folge 
vom Fibonacci-Typ ist. 
Der Trick ist dann, danach zu fragen, 
f"ur welche $\beta$ die Folge  $x_i \pdef\beta^i$
vom Fibonacci-Typ ist.
Das ist ja offensichtlich genau dann der Fall, wenn gilt 
$ \beta^2= \beta+1 $, als da hei"st f"ur
$\beta_{\pm} = \frac{1}{2} (1 \pm \sqrt{5})$. F"ur beliebige
$c,d$ ist mithin die Folge
\begin{displaymath}
x_i = c\beta_+^i + d\beta_-^i
\end{displaymath}
vom Fibonacci-Typ, und 
wenn wir $c $ und $d$  bestimmen
mit $x_0 = 0$ und $x_1 =1$, so ergibt sich eine explizite Darstellung unserer 
Fibonacci-Folge.
Wir suchen also $c$ und $d$ mit
\begin{displaymath}
\begin{array}{lll}
0 &=& c + d\\
1 & =& c \left( \frac{1}{2}(1+\sqrt{5})\right) + d
\left( \frac{1}{2} (1-\sqrt{5})\right)
\end{array}
\end{displaymath}
und folgern leicht $c = -d$ und $1 = c\sqrt{5} $ alias
$c =  1/\sqrt{5}=-d$. Damit ergibt sich schlie"slich
f"ur unsere urspr"ungliche Fibonacci-Folge die explizite Darstellung
\begin{displaymath}
f_i = \frac{1}{\sqrt{5}} \left( \frac{1+ \sqrt{5}}{2}\right)^i 
- \frac{1}{\sqrt{5}}
\left( \frac{1-\sqrt{5}}{2}\right)^{i}
\end{displaymath}
Im "ubrigen ist der zweite Summand hier immer kleiner als
$1/2$, so da"s wir $f_i$ auch beschreiben k"onnen als diejenige
ganze Zahl, die am n"achsten am ersten Summanden liegt. 
Es w"are r"uckblickend nat"urlich ein Leichtes gewesen, 
diese Formel einfach zu \glqq raten\grqq,  um sie dann mit vollst"andiger Induktion
\ref{ErF} zu beweisen. Diese Art mathematischer Zaubertricks halte
ich jedoch f"ur unehrenhaft. Ich denke, unsere Aufgabe
als Mathematiker besteht darin, Verst"andnis zu erzeugen
und nicht Bewunderung.
Ich  werde deshalb stets nach Kr"aften versuchen, 
das Tricksen zu vermeiden, auch wenn die Beweise dadurch 
manchmal etwas l"anger werden sollten.
Eine M"oglichkeit, auch den letzten verbleibenden Trick 
aus den vorhergehenden "Uberlegungen zu eliminieren, zeigt \eref{FiAl}{LA1}.
Die bei unserer L"osung 
auftretende reelle Zahl $\frac{1}{2} (1 + \sqrt{5})$ 
ist im "Ubrigen auch bekannt als 
\glqq goldener Schnitt\grqq\  aus Gr"unden, die in nebenstehendem Bild 
diskutiert werden.
In \eref{UGF}{AN1} d"urfen Sie dann zur "Ubung zeigen, da"s der Quotient
zweier aufeinanderfolgender 
Fibonacci-Zahlen 
gegen den goldenen Schnitt strebt, da"s also genauer und in Formeln
f"ur unsere Fibonacci-Folge $f_0,f_1,f_2,\ldots$ von oben gilt 
$$\lim_{i\ra\infty}\frac{f_{i+1}}{f_i}=\frac{1 + \sqrt{5}}{2} $$
\end{Beispiel}
\begin{fBild}[p]\centering
\includegraphics[width=\textwidth]{SkriptenBilder/BildGSc}\\[4mm]
\noindent 
Der {\bf goldene Schnitt}\index{goldener Schnitt} 
ist das Verh"altnis, in dem eine
Strecke geteilt werden mu"s, damit das Verh"altnis vom
gr"o"seren zum kleineren St"uck gleich dem Verh"altnis 
des Ganzen zum gr"o"seren St"uck ist, also die positive L"osung
der Gleichung
$a/1 = (1+a) /a$ alias $a^{2}-a-1 =0$,
also $a=(1+\sqrt{5})/2$.
\end{fBild}


\begin{Beispiel}\label{AlgVe}
  Wir betrachten das
Gleichungssystem 
\begin{displaymath}
\begin{array}{lll}
3 x + 3y +  7z&=&0\\
4 x +\;\; y +  5z&=&0
\end{array}
\end{displaymath}
Wie man die Menge $L$ aller L"osungen $(x,y,z)$ ermittelt, sollen
sie sp"ater in dieser Vorlesung lernen. Zwei Dinge aber sind a priori klar:
\begin{enumerate}
\item Sind $(x,y,z) $ und $(x',y',z')$ L"osungen, so ist
  auch ihre komponentenweise Summe
$(x + x', y+y',z+z')$ eine L"osung;
\item Ist $(x,y,z)$ eine L"osung und $\alpha$ eine reelle Zahl, so
  ist auch das komponentenweise Produkt
$(\alpha x, \alpha y, \alpha z)$ eine L"osung.
\end{enumerate}
\end{Beispiel}



\begin{Beispiel}
  Wir betrachten die Menge aller Funktionen $f: \Bbb{R} \ra \Bbb{R}$, die
  zweimal differenzierbar sind und der Differentialgleichung
\begin{displaymath}
f''  = - f
\end{displaymath}
gen"ugen. L"osungen sind zum Beispiel die Funktionen $\sin, \cos$, die
Nullfunktion oder auch die Funktionen $f(x) = \sin (x+a)$ f"ur konstantes $a$.
Wie man die Menge $L$ aller L"osungen beschreiben kann, 
sollen Sie in der Analysis lernen.
Zwei Dinge aber sind a priori klar:
\begin{enumerate}
\item Mit $f$ und $g$ ist auch die Funktion $f+g$ eine L"osung;
\item Ist $f$ eine L"osung und $\alpha$ eine reelle 
Zahl, so ist auch $\alpha f$
  eine L"osung.
\end{enumerate}
\end{Beispiel}


\begin{Beispiel}\label{VeFe}
Wir betrachten die Gesamtheit aller Parallelverschiebungen 
der Tafelebene. Graphisch stellen wir
solch eine Parallelverschiebung dar durch einen Pfeil von 
irgendeinem Punkt zu seinem
Bild unter der Verschiebung. Im nebenstehenden Bild 
stellen etwa alle gepunktelten Pfeile
dieselbe Parallelverschiebung dar.
Was f"ur ein Ding diese Gesamtheit $P$ aller 
Parallelverschiebungen eigentlich ist, scheint mir recht undurchsichtig,
aber einiges ist a priori klar:
\begin{enumerate}
\item Sind $p$ und $q$ Parallelverschiebungen, so ist auch ihre
  \glqq Hintereinanderausf"uhrung\grqq\  $p \circ q$, sprich \glqq $p$ nach $q$\grqq, eine
  Parallelverschiebung.
\begin{fBild}[p]
  \centering
  \includegraphics[width=\textwidth]{SkriptenBilder/BildPar}\\[4mm]
\noindent
Die Hintereinanderausf"uhrung der beiden Parallelverschiebungen
der Tafel- oder hier vielmehr der Papierebene, die durch die
durchgezogenen Pfeile dargestellt werden, wird die durch die
gepunktelten Feile dargestellt.
\end{fBild}
\item Ist $\alpha$ eine reelle Zahl und $p$ eine Parallelverschiebung, so
  k"onnen wir eine neue Parallelverschiebung $\alpha p$ bilden, das
  \glqq $\alpha$-fache von $p$\grqq.  Bei negativen Vielfachen vereinbaren wir hierzu,
  da"s damit eine entsprechende Verschiebung in die Gegenrichtung gemeint ist.
\item 
F"uhren wir eine neue Notation ein und schreiben
f"ur die Hintereinanderausf"uhrung
$p\dotplus q\pdef p\circ q$, so gelten f"ur beliebige   Parallelverschiebungen
  $p,q,r$ der Tafelebene und beliebige reelle\label{VeFee} 
Zahlen $\alpha, \beta$ die Formeln
\begin{displaymath}
\begin{array}{ccc}
(p \dotplus q) \dotplus r & =& p \dotplus (q \dotplus r)\\
p\dotplus q & = & q \dotplus p\\
\alpha (\beta p) & =& (\alpha \beta )p\\
(\alpha + \beta) p & =& (\alpha p)\dotplus (\beta p)\\
\alpha (p \dotplus q) & =& (\alpha p) \dotplus (\alpha q)
\end{array}
\end{displaymath}
\end{enumerate}
Will man sich die Gesamtheit aller Parallelverschiebungen der Tafelebene
anschaulich machen, so tut man im "Ubrigen 
gut daran, einen Punkt als \glqq Ursprung\grqq\ 
auszuzeichnen und jede Parallelverschiebung mit dem Punkt der Tafelebene zu
identifizieren, auf den unsere Parallelverschiebung diesen Ursprung abbildet. 
\end{Beispiel}
\begin{Beispiel}
  Analoges gilt f"ur die Gesamtheit der Parallelverschiebung des Raums 
unserer Anschauung und\label{ZSV}  
auch f"ur die Gesamtheit aller Verschiebungen einer Geraden und, mit
  noch mehr Mut, f"ur die Gesamtheit aller Zeitspannen.
\end{Beispiel}



\begin{Bemerkungl}\label{kpl}
Die  Formeln unserer kleinen Formelsammlung 
von \ref{VeFe}.\ref{VeFee} gelten ganz genauso auch f"ur die 
L"osungsmenge unserer Differentialgleichung $f''  = -f$, 
wenn wir $f\dotplus g \pdef  f + g$
verstehen, f"ur die L"osungsmenge unseres linearen 
Gleichungssystems, wenn wir 
$$(x, y, z ) \dotplus (x', y' , z') 
\pdef  (x + x', y+y' , z+z')$$
als \glqq komponentenweise Addition\grqq\  verstehen, 
und f"ur die Menge aller Folgen vom Fibonacci-Typ, wenn wir 
"ahnlich die Summe $\dotplus$ zweier Folgen erkl"aren.
Ein wesentliches Ziel der Vorlesungen "uber lineare Algebra 
ist es, einen abstrakten 
Formalismus aufzubauen, dem sich alle
diese Beispiele unterordnen. Dadurch soll
Zweierlei erreicht werden:
\\[2mm]\noindent
1. Unser abstrakter Formalismus  soll uns dazu verhelfen, 
die uns als Augentieren und Nachkommen von "Asteh"upfern 
angeborene r"aumliche Anschauung nutzbar zu machen
zum Verst"andnis der bis jetzt gegebenen Beispiele 
und der vielen weiteren Beispiele  von Vektorr"aumen,
denen Sie im  Verlauf Ihres  Studiums 
noch begegnen werden.
So werden sie etwa lernen, da"s man sich die Menge aller  
Folgen vom Fibonacci-Typ durchaus als Ebene 
vorstellen darf und die Menge
aller Folgen mit einem vorgegebenem Folgenglied
an einer vorgegebenen Stelle als eine
Gerade in dieser Ebene.
Suchen wir also alle Folgen vom Fibonacci-Typ  mit zwei vorgegebenen 
Folgengliedern,
so werden wir im allgemeinen genau eine derartige 
L"osung finden, da sich eben zwei Geraden
aus einer Ebene im allgemeinen in genau einem Punkt 
schneiden. In diesem Licht betrachtet soll der abstrakte
Formalismus uns also helfen,  a priori unanschauliche 
Fragestellungen der Anschauung 
zug"anglich zu machen. Ich denke, diese N"ahe zur
Anschauung ist auch der Grund daf"ur, da"s die lineare
Algebra meist
an den Anfang des Studiums gestellt wird: 
Von der Schwierigkeit des Formalismus her gesehen
geh"ort sie n"amlich keineswegs zu den einfachsten Gebieten der 
Mathematik. Hier w"urde ich eher an Gruppentheorie oder Graphentheorie
oder dergleichen 
denken.
\\[2mm]\noindent
2. Unser 
abstrakter Formalismus soll so unmi"sverst"andlich 
sein und seine Spielregeln so klar,
da"s Sie in die Lage versetzt werden,
alles nachzuvollziehen und mir im Prinzip 
und vermutlich auch in der Realit"at  Fehler
nachzuweisen. Schwammige Begriffe wie \glqq Tafelebene\grqq\  
oder \glqq Parallelverschiebung des Raums\grqq\ 
haben in einem solchen Formalismus keinen Platz mehr.
In diesem Licht betrachtet verfolgen wir mit dem Aufbau
des abstrakten Formalismus
auch das Ziel einer gro"sen Vereinfachung durch die Reduktion auf
die Beschreibung einiger weniger Aspekte der uns umgebenden 
in ihrer Komplexit"at schwer fa"sbaren Wirklichkeit.
\\[2mm]\noindent
Die lineare Algebra hat in meinen Augen mindestens drei wesentliche Aspekte:
Einen {\bf geometrischen Aspekt}, wie ihn  das Beispiel \ref{VeFe}
der Gesamtheit aller Parallelverschiebungen illustriert;
einen {\bf algorithmischen Aspekt}, unter den ich  das Beispiel
\ref{AlgVe} der L"osungsmenge eines linearen Gleichungssystems und 
insbesondere explizite Verfahren zur Bestimmung dieser
L"osungsmenge einordnen w"urde; und einen 
{\bf abstrakt-algebraischen Aspekt}, zu dem etwa die 
folgende Definition \ref{DERv} geh"ort,
eine Art gedankliches Skelett,
das Algorithmik und Geometrie 
verbindet und 
Br"ucken zu vielen weiteren Anwendungen schafft, die man 
dann als das Fleisch auf diesem Gerippe ansehen mag.
Ich will im  Verlauf meiner Vorlesungen zur linearen Algebra
versuchen, 
diese drei Aspekte zu einer Einheit zu f"ugen. Ich hoffe,  da"s Sie
dadurch 
in die Lage versetzt werden,  eine Vielzahl von Problemen 
mit den verbundenen Kr"aften Ihrer r"aumlichen Anschauung,
Ihrer algorithmischen Rechenf"ahigkeiten und Ihres abstrakt-logischen
Denkens anzugehen.
Als Motivation f"ur den weiteren Fortgang der Vorlesungen "uber lineare
Algebra beschreibe ich nun das \glqq R"uckgrat unseres Skeletts\grqq\ 
und formuliere  ohne R"ucksicht
auf noch unbekannte Begriffe und Notationen  die abstrakte 
Definition eines reellen Vektorraums.
\end{Bemerkungl}
\begin{Definition}\label{DERv}
Ein \defind{reeller Vektorraum} ist ein Tripel bestehend aus
den folgenden drei Dingen:
\begin{enumerate}
\item
Einer Menge $V$;
\item
Einer Verkn"upfung $V \times V \ra V$, $ (v, w) \mapsto v \dotplus w$,
die die Menge $V$ zu einer abelschen Gruppe macht;
\item
Einer Abbildung $\Bbb{R} \times V \ra V$, $ (\alpha , v) \mapsto \alpha v$,
\end{enumerate}
derart, da"s f"ur alle $\alpha, \beta \in \Bbb{R}$ und alle $v,w \in V$ gilt:
\begin{displaymath}
\begin{array}{ccc}
\alpha (\beta v) &=& (\alpha \beta) v\\
(\alpha + \beta) v &=& (\alpha v) \dotplus (\beta v)\\
\alpha (v\dotplus w) &=& (\alpha v) \dotplus (\alpha w)\\
1v &=& v
\end{array}
\end{displaymath}
  Hier ist nun viel zu kl"aren: Was ist eine Menge?  Eine Verkn"upfung? Eine
  abelsche Gruppe?  Eine Abbildung? Was bedeuten die 
Symbole $\times $, $\ra$, $\mapsto $,
  $\in $, $\Bbb{R}$?  Wir beginnen in der n"achsten Vorlesung mit 
der Kl"arung dieser Begriffe und Notationen.
\end{Definition}

\begin{Bemerkungl}
 Bereits hier will ich  die Symbole $\alpha$ und $\beta$ 
erkl"aren: Sie hei"sen \glqq Alpha\grqq\  und \glqq Beta\grqq\  und sind die beiden ersten
Buchstaben des griechischen Alphabets, das ja hinwiederum selbst nach ihnen benannt ist.
Bei der Darstellung von
 Mathematik hilft es, viele verschiedene Symbole und Symbolfamilien
zur Verf"ugung zu haben.
Insbesondere werden die griechischen Buchstaben oft und gerne verwendet.
Ich schreibe deshalb hier zum Nachschlagen
das griechische Alphabet auf.\index{griechisches Alphabet}
In der ersten Spalte\index{Alphabet, griechisches}
stehen der Reihe nach die griechischen Kleinbuchstaben,
dahinter die zugeh"origen Gro"sbuchstaben, dann ihr lateinisches Analogon
soweit vorhanden, und schlie"slich, wie man diesen griechischen Buchstaben
auf Deutsch benennt und spricht.
$$\begin{array}{llll}
\alpha&\text{A}&\text{a}&\text{alpha}\\
\beta&\text{B}&\text{b}&\text{beta}\\
\gamma&\Gamma&\text{g} &\text{gamma}\\
\delta&\Delta& \text{d}&\text{delta}\\
\epsilon,\varepsilon&  \text{E}& \text{e}&\text{epsilon}\\
\zeta& \text{Z}& \text{z}&\text{zeta}\\
\eta&\text{H} &\text{"a} &\text{eta}\\
\theta,\vartheta&\Theta& \text{th} &\text{theta}\\
\iota& \text{I}&\text{i} &\text{iota}\\
\kappa&\text{K} & \text{k}&\text{kappa}\\
\lambda&\Lambda&  \text{l}&\text{lambda}\\
\mu&\text{M} &\text{m}&\text{my, sprich \glqq m"u\grqq\ }\\
\nu& \text{N}& \text{n}&\text{ny, sprich \glqq n"u\grqq\ }\\
\xi& \Xi& \text{x}&\text{xi}\\
o & \text{O}&\text{o}&\text{omikron, \glqq kurzes o\grqq}\\
\pi& \Pi & \text{p}&\text{pi}\\
%\varpi&&  &\text{varpi}\\
\rho,\varrho& \text{P}& \text{r}&\text{rho}\\
\sigma,\varsigma&\Sigma& \text{s} &\text{sigma}\\
\tau& \text{T}&\text{t} &\text{tau}\\
\upsilon&\Upsilon& \text{y} &\text{ypsilon}\\
\phi,\varphi& \Phi&\text{f}&\text{phi}\\
\chi&\text{X }&\text{ch}&\text{chi}\\
\psi& \Psi&\text{ps} &\text{psi}\\
\omega&\Omega& \text{oh}&\text{omega, \glqq langes o\grqq}\\


\end{array}$$
\end{Bemerkungl}
\subsubsection*{"Ubungen}
\begin{Ubung}\label{ZSFF} 
  Ein Kredit von $10000$ Euro wird am Ende jeden Jahres mit
einem j"ahrlichen Zinssatz von $5\%$ auf die jeweilige Restschuld 
verzinst und der Kreditnehmer zahlt zu Beginn jeden Jahres $1000$ Euro 
zur"uck. Man finde eine geschlossene 
Formel f"ur die Restschuld am Ende des $n$-ten Jahres. Hinweis: Man mag 
es mit dem Ansatz $x_n=c\beta^n+\alpha$ versuchen. 
\end{Ubung}

\begin{Ubung}\label{ZSFFv} 
Kann man f"ur jede Folge $x_0,x_1,\ldots$ vom Fibonacci-Typ 
Zahlen $c,d$ finden mit $x_i = c\beta_+^i + d\beta_-^i$ f"ur alle $i$?
Finden Sie eine geschlossene Darstellung f"ur die Glieder der Folge,
die mit $0,0,1$ beginnt und dem Bildungsgesetz
$x_n=2x_{n-1}+x_{n-2}-2x_{n-3}$ gehorcht.
\end{Ubung}
\begin{Ubung}
  Die Fibonnacci-Folge  erf"ullt die Identit"at
  $f_0^2+f_1^2+\ldots+f_k^2=f_kf_{k+1} $
  f"ur alle $k\geq 0$. 
\end{Ubung}
\newpage
\begin{Ubung}
\begin{quote}
Wer Alles mit $\varphi$l $\mu$ ka$\pi$rt,
hat eine g$\rho$"s$\eta$t g$\eta$n.\\
Wer Hausis nur ko$\pi$rt,
steht am P$\rho\beta$g hintan.
\end{quote}

\begin{quote}
Gestern standen wir noch vor einem tiefen Abgrund,\\
aber heute haben wir einen g$\rho$"sen Schritt nach vorne g$\eta$n
\end{quote}

\begin{quote}
Liebe ist, wenn sich der $\tau$sendste Kuss
noch wie der erste an$\varphi$lt.
\end{quote}

\begin{quote}
Nach dem Takt,
den man t$\rho$mmelt,
wird auch g$\eta$nzt.
\end{quote}

\begin{quote}
Vorg$\eta$n und nach$\beta$cht\\
hat manchem schon g$\rho$"s Leid gebracht.
\end{quote}

\begin{quote}Was mit wenigem abg$\eta$n werden kann,\\
muss nicht mit $\varphi$lem g$\eta$n werden.
\end{quote}

\begin{quote}Als ich eine $\rho$se brach,\\
und mir in den $\varphi$nger stach\dots 
\end{quote}

\begin{quote}$\tau$send Freunde sind zu wenig,\\
ein Feind jedoch ist zu $\varphi$l
\end{quote}
\end{Ubung}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "XXEIN"
%%% End: