% 
% hw1.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{amsmath, amssymb}
\usepackage{color}

\newcommand{\nn}{\nonumber\\}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.75in}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Homework 9 (optional: won't be graded)\\[2ex]
       \rm\normalsize ECS 20 (Winter 2019)}
%\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1: 10 points} 

Using induction, show that $\forall n \in \mathbb{N}, \displaystyle \sum_{i=1}^{n}i^3 = \left( \displaystyle\frac{n(n+1)}{2} \right) ^2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2: 10 points} 

Using induction, show that $\forall n \in \mathbb{N}, \displaystyle\sum_{i=1}^{n}i(i+1)(i+2) = \displaystyle\frac{n(n+1)(n+2)(n+3)}{4} $.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3: 10 points} 

Show that $\forall n \in \mathbb{N}, n>1, \displaystyle\sum_{i=1}^{n}\displaystyle\frac{1}{i^2}<2-\displaystyle\frac{1}{n}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4: 10 points} 

Show that $\forall n \in \mathbb{N}, n>3,   n^2-7n+12\geq 0$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5: 10 points} 

Show that $\forall n \in \mathbb{N}, n>1$, a set $S_n$ with $n$ elements has $\displaystyle\frac{n(n-1)}{2}$ subsets that contain exactly two elements.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6: 10 points} 

Find the flaw with the following proof that $: P(n): a^n=1$ for all non negative integer $n$, whenever $a$ is a non zero real number:
\begin{itemize}
\item \emph{Basis step:}  $P(0)$ is true: $a^0=1$  is true, by definition of $a^0$
\item \emph{Strong Inductive step:} assume that $a^j=1$ for all non negative integers $j$ with $j \leq k$. Then note that:
\begin{eqnarray*}
a^{k+1} = \frac{a ^k a^k}{a^{k-1}} = \frac{1\times1}{1} = 1
\end{eqnarray*}
Therefore $P(k+1)$ is true.
\end{itemize}
The principle of proof by strong mathematical induction allows us to conclude that $P(n)$ is true for all $n\geq 0$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 7: 10 points} 

Show that $\forall n \in \mathbb{N}$, 21 divides $4^{n+1}+5^{2n-1}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 8: 10 points} 

Show that $\forall n \in \mathbb{N} f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$ where $f_n$ are the Fibonacci numbers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 9: 10 points} 

Show that $\forall n \in \mathbb{N}  f_0-f_1+f_2-\ldots-f_{2n-1}+f_{2n}=f_{2n-1}-1$ where $f_n$ are the Fibonacci numbers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Extra Credit: 5 points} 

Show that $\forall n \in \mathbb{N}, n>1$, a set $S_n$ with $n$ elements has $\displaystyle\frac{n(n-1)(n-2)}{6}$ subsets that contain exactly three elements.

\end{document}