
\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}

 \title{Lektion 03-11}


\begin{document}
\maketitle
\section*{Rekursion}

En {\it talf\"oljd} kan defineras genom att man anger en explicit formel. Till exempel betrakta sekvensen $$\{a_n=n^2\}_{n\in\nat}$$

Men det \"ar mycket vanligt att talf\"oljden defineras via en {\it rekursions formula}. Det betyder att man anger hur varje element kan ber\"aknas ur den f\"oreg\aa ende element. Ett exempel \"ar:
$$a_n=a_{n-1}+2n-1\text{ f\"or }n\geq 1\text{ och } a_0=0$$
$a_0=0$ kallas begynnelsev\"arde.

Detta anger f\"oljden $\{0,1,4,9,16,...\}$.

Man kan ha mer komplicerade rekursion formuler. {\it Fibonaccif\"oljden} \"ar ett exempel p{\aa} f\"oljd d\"ar man behover tv{\aa} f\"oreg\aa ende element f\"r att ber\"akna den f\"oljande element:

\[\left\{\begin{array}{llll}
F_n&=&F_{n-1}+F_{n-2}&\hspace{.2in}n\geq 2\\
F_1&=&1&\\
F_0&=&0&
\end{array}
\right.\]

\vspace{.1in}

 


\section*{Induktion}

Vi ska anv\"anda symboler $\sum$ och $\Pi$ p{\aa} f\"oljande s\"att.
\begin{itemize}
\item $\sum_{i=1}^n s_i=s_1+...+s_n$
\item $\Pi_{i=1}^n s_i=s_1\cdot ... \cdot s_n$.
\end{itemize}

\vspace{.in}


\noindent{\it Exempel}.
$$\sum_{i=1}^n i^2=1+4+9+16+...+n^2$$
Vi har att
\begin{itemize}
\item Om $n=1$ d{\aa} blir summan $1=\frac{1(1+1)(2\cdot 1+1)}{6}$,
\item Om $n=2$ d{\aa} blir summan $5=\frac{2(1+2)(2\cdot 2+1)}{6}$,
\item Om $n=3$ d{\aa} blir summan $14=\frac{3(1+3)(2\cdot 3+1)}{6}$.
\end{itemize}
\noindent{\it Hur kan man visa att}:
$$\sum_{i=1}^n i^2=\frac{n(1+n)(2\cdot n+1)}{6}\text{ g\"aller f\"or  }n\geq 1?$$

N\"ar vi vill visa att en sats $P(n)$ g\"aller f\"or alla naturliga tal $n\geq a$  \"ar det ofta bra att anv\"anda {\it INDUKTIONSPRINCIPEN}:
\begin{enumerate}
\item visa $P(a)$ g\"aller, dvs visa att satsen \"ar sant f\"or $n=a$. Detta kallas {\it bassteget}.
\item Antag $P(n)$ g\"aller f\"or $n\leq k$ och visa $P(k+1)$, dvs antag att satsen \"ar sant f\"or $n\leq k$ och visa sedan den for $n=k+1$
\end{enumerate}

N\"ar man har verifierat steg (1) och (2) har man , enligt induktions pricipen, visat satsen g\"aller f\"or alla $n\geq a$.

\vspace{.1in}

\noindent BEVIS: Vi ska bevisa  att $\sum_{i=1}^n i^2=\frac{n(1+n)(2\cdot n+1)}{6}\text{ f\"or  }n\geq 1$.
\begin{enumerate}
\item Detta \"ar sant f\"or $n=1$ (vi ber\"aknade det).
\item Antag att 
$$\sum_{i=1}^n i^2=\frac{n(1+n)(2\cdot n+1)}{6}\text{ g\"aller f\"or }n\leq k$$
Vi ska visa att 
$$\sum_{i=1}^{k+1} i^2=\frac{(k+1)(1+k+1)(2\cdot (k+1)+1)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$$
Vi har att:
$$\sum_{i=1}^{k+1} i^2=\sum_{i=1}^k i^2+(k+1)^2=\frac{k(1+k)(2\cdot k+1)}{6}+(k+1)^2$$
Och d{\aa}
$$\sum_{i=1}^{k+1} i^2=\frac{(1+k)[k(2\cdot k+1)+6(k+1)]}{6}=\frac{(1+k)(2k^2+7k+6)}{6}=$$
$$=\frac{k+1(1+k+1)(2\cdot (k+1)+1)}{6}$$
\end{enumerate}
S{\aa}, enligt induktionsprincipen g\"aller  $\sum_{i=1}^n i^2=\frac{n(1+n)(2\cdot n+1)}{6}$ f\"or  alla $n\geq 1$.

\vspace{.1in}

\noindent{\it Exempel}: Beviset av en del av v\"alordningspricipen. 

Vi vill visa att alla icke-tomma \"andliga delm\"angder  $B$ av $\zed^+$ inneh\aa ller ett minsta element.

Vi ska visa den med h\"alp av induktion p{\aa} kardinaliteten av delm\"agden.
\begin{enumerate}
\item Om $|B|=0$ det finns ingenting att visa, s{\aa} satsen \"ar sant.
\item Antag att satsen \"ar sant f\"or varje delm\"angd $B$ med kardinaliteten $\leq k$. Vi ska visa att satsen \"ar sant f\"or varje $B$ med $|B|=k+1$.
Betrakta en delm\"angd $B=\{a_1,...,a_{k+1}\}$. Enligt induktionsantagandet har delm\"angden $\{a_1,...,a_{k}\}$ ett minsta element $m$. Om $m\leq a_{k+1}$ s{\aa} \"ar $m$ det minsta element av $B$. Annars \"ar $a_{k+1}<m$ som betyder att $a_{k+1}$ \"ar det minsta element av $B$.
\end{enumerate} 

\vspace{.1in}

\noindent{\it Exempel}. Visa att $n^2>7n+1$ f\"or alla $n\geq 8$.

\begin{enumerate}
\item Satsen \"ar sant f\"or $n=8$ eftersom $64>56+1$.
\item Antag $n^2>7n+1$ f\"or alla $n\leq k$. Vi ska visa att $(k+1)^2>7(k+1)+1$. P{\aa} grund av induktionsantagandet \"ar $(k+1)^2=k^2+2k+1>7k+1+2k+1$. D{\aa} 2k-6har vi att $(k+1)^2>7(k+1)+1+(2k-6)>7(k+1)+1$ eftersom $k\geq 8$ g\"aller $2k-6>0$.  
\end{enumerate}

\vspace{.1in}

\noindent{\it Exempel}. Visa att $6$ \"ar en delare till alla heltal p{\aa} formen $8^n-2^n$, f\"or $n\in\zed^+$.

\begin{enumerate}
\item Satsen \"ar sant f\"or $n=1$ eftersom $6|8-2$.
\item Antag  att $6|8^n-2^n$ f\"or alla $n\leq k$. Vi ska visa att  $6|8^{k+1}-2^{k+1}$. P{\aa} grund av induktionsantagandet \"ar $8^k-2^{k}=6h$ d\"ar $h\in\zed$. Det f\"oljer att:
$$8^{k+1}=8\cdot 8^k=8(2^{k}+6h)=(2+6)(2^{k}+6h)=2(2^{k}+6h)+6(2^{k}+6h)=2^{k+1}+6(18h+2^{k})$$
S{\aa} $8^{k+1}-2^{k+1}=6(18h+2^{k})$  som betyder att $6|8^{k+1}-2^{k+1}$
\end{enumerate}

\section*{\"ovning}
\begin{enumerate}
\item R\"akna upp elementen av Fibonaccif\"oljden.
\item Visa, med hj\"alp av induktion, att $n!>2^n$ f\"or $n\geq 4$.
\item Visa att $$\sum_{i=n}^{2n-1}(2i+1)=3n^2\text{ f\"or alla }n\in\zed^+$$ 
\end{enumerate}

\end{document}