\documentclass{article}

\usepackage{fullpage}
\usepackage{algpseudocode}
\usepackage{amsmath}

\begin{document}



\paragraph{Example}

\begin{algorithmic}
\For{$i = 1 \ldots n$}
	\For{$j = 1 \ldots i$}
		\State do work
	\EndFor
\EndFor
\end{algorithmic}

How many times do we ``do work''?
\[ 1 + 2 + 3 + \ldots + n = \sum_{i=1}^{n} i \]

Claim: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Proof (by induction): 

Base Case: $n = 1$.

\[ \sum_{i=1}^{1} i = 1 = \frac{1(1 + 1)}{2} \]

Inductive Case: show that if $\sum_{i=1}^{k} =  \frac{k(k+1)}{2}$ then $\sum_{i=1}^{k+1} =  \frac{(k+1)(k+2)}{2}$.

\begin{align*}
\sum_{i=1}^{k} i &=  \frac{k(k+1)}{2} \\
1 + 2 + \ldots + n &=  \frac{k(k+1)}{2} \\
1 + 2 + \ldots + n + (n+1) &=  \frac{k(k+1)}{2} + (k+1)\\
\sum_{i=1}^{k+1} i &=  \frac{k(k+1)}{2} + (k+1)\\
\sum_{i=1}^{k+1} i &=  \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\
\sum_{i=1}^{k+1} i &=  \frac{k(k+1) + 2(k+1)}{2} \\
\sum_{i=1}^{k+1} i &=  \frac{(k+1)(k+2)}{2} \\
\end{align*}

So by induction, our formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ holds for all positive integers $n$.




\paragraph{Exercise}



\begin{algorithmic}
\For{$i = 1 \ldots n$}
	\For{$j = 1 \ldots i^2$}
		\State do work
	\EndFor
\EndFor
\end{algorithmic}


How many times do we ``do work''?
\[ 1 + 4 + 9 + \ldots + n^2 = \sum_{i=1}^{n} i^2 \]

Show using induction that $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1}{6}$.



\paragraph{Example}

\begin{algorithmic}
\Function{Fact}{n}
	\If{$n == 0$}
		\State \Return 1
	\EndIf
	\State \Return $n$ * \Call{Fact}{$n-1$}
\EndFunction
\end{algorithmic}

Claim: this function correctly computes factorial. Proof (by induction):

Base case: $n=0$.

\[\textsc{Fact}(0) = 1 = 0! \]

Inductive case:
\begin{itemize}
\item Assume: $\textsc{Fact}(k) = k!$
\item Goal: $\textsc{Fact}(k+1) = (k+1)!$
\end{itemize}


\begin{align*}
\textsc{Fact}(k+1) &=  \textsc{Fact}(k) * (k+1) \\
\textsc{Fact}(k+1) &=  k! * (k+1) \\
\textsc{Fact}(k+1) &=  (k+1)! \\
\end{align*}

So by induction, our function \textsc{Fact} computes factorial correctly for any non-negative integer $n$.





\paragraph{Exercise}

\begin{algorithmic}
\Function{contains}{arr, n, val}
	\If{$n == 0$}
		\State \Return false
	\EndIf
	\If{arr[n-1] == val}
		\State \Return true
	\EndIf
	\State \Return \Call{contains}{arr, n-1, val}
\EndFunction
\end{algorithmic}


Show using induction that \textsc{contains} correctly determines whether the array $arr$ contains the value $val$ for any array, length ($n$), and value.

\end{document}