% 
% 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): Solutions\\[2ex] 
       \rm\normalsize ECS 20 (Winter 2019)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1} 

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

\vspace{0.2in}

Let $P(n)$ be the proposition: $\displaystyle\sum_{i=1}^{n}i^3 = \left( \displaystyle\frac{n(n+1)}{2} \right) ^2$. Let us also define $LHS(n) = \displaystyle\sum_{i=1}^{n}i^3$ and $RHS(n)=\left( \displaystyle\frac{n(n+1)}{2} \right) ^2$
\\
\begin{itemize}
\item \emph{Basis step:} $P(1)$ is true:
\begin{eqnarray*}
LHS(1) &=&\sum_{i=1}^{1} i^{3} = 1\\
RHS(1)&=&\left(\frac{1(1+1)}{2}\right)^{2} = \left(\frac{2}{2}\right)^{2}=1
\end{eqnarray*}
\\
\item \emph{Inductive step:} Let $k$ be a positive integer ($k\leq 0$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let us compute $LHS(k+1)=\displaystyle\sum_{i=1}^{k+1}i^3$:\\
\begin{eqnarray*}
LHS(k+1) &=& \displaystyle\sum_{i=1}^{k} i^{3} + (k+1)^{3}\\
&=& \left(\frac{k(k+1)}{2}\right)^{2} + (k+1)^{3}\\
&=& \frac{k^{2}}{4}(k+1)^{2} + (k+1)(k+1)^{2}\\
&=& \frac{k^{2} + 4k + 4}{4} (k+1)^{2}\\
&=& \frac{(k+2)^{2}}{4} (k+1)^{2}\\
&=& \left(\frac{(k+1)(k+2)}{2}\right)^{2}
\end{eqnarray*}
And:
\begin{eqnarray*}
RHS(k+1) = \left( \frac{ (k+1)(k+2)}{2} \right)^2
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$, which validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2} 

\textcolor{blue}{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} $}.

\vspace{0.2in}


Let $P(n)$ be the proposition: $\displaystyle\sum_{i=1}^{n}i(i+1)(i+2) = \displaystyle\frac{n(n+1)(n+2)(n+3)}{4} $. We define $LHS(n)= \displaystyle\sum_{i=1}^{n}i(i+1)(i+2)$ and $RHS(n)=\displaystyle\frac{n(n+1)(n+2)(n+3)}{4} $
\\
\begin{itemize}
\item \emph{Basis step:} $P(1)$ is true:
\begin{eqnarray*}
LHS(1) &=& 1\ast(1+1)\ast(1+2) = 6 \\
RHS(1) &=& \frac{ 1\ast(1+1)\ast(1+2)\ast(1+3)}{4} = 6
\end{eqnarray*}


\item \emph{Inductive step:} Let $k$ be a positive integer ($k\leq 0$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let us compute $LHS(k+1)$:
\begin{eqnarray*}
LHS(k+1) &=& =\sum_{i=1}^{k+1}i(i+1)(i+2) \\
&=& LHS(k) + (k+1)(k+2)(k+3) \\
&=& \frac{k(k+1)(k+2)(k+3)}{4} + (k+1)(k+2)(k+3) \\
&=& \frac{k(k+1)(k+2)(k+3)}{4} + \frac{4(k+1)(k+2)(k+3)}{4}\\
&=& \frac{(k+1)(k+2)(k+3)(k+4)}{4}
\end{eqnarray*}
Let us compute $RHS(k+1)$:
\begin{eqnarray*}
RHS(k+1) &=& \frac{(k+1)(k+2)(k+3)(k+4)}{4}
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$, which validates that $P(k+1)$ is true.\\
\end{itemize}

The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3} 

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

\vspace{0.2in}


Let $P(n)$ be the proposition: $\displaystyle\sum_{i=1}^{n}\displaystyle\frac{1}{i^2}<2-\displaystyle\frac{1}{n}$. Let us define $LHS(n) = \displaystyle\sum_{i=1}^{n}\displaystyle\frac{1}{i^2}$ and $RHS(n)=2-\displaystyle\frac{1}{n}$. We want to show that $P(n)$ is true for all $n>1$.
\\
\begin{itemize}
\item \emph{Basis step:} We show that $P(2)$ is true:\\
\begin{eqnarray*}
LHS(2) = 1 + \frac{1}{4} = \frac{5}{4} \\
RHS(2) = 2 - \frac{1}{2} = \frac{6}{4}
\end{eqnarray*}
Therefore $LHS(2) < RHS(2)$ and $P(2)$ is true.
\item \emph{Inductive step:} Let $k$ be a positive integer greater than 1 ($k> 1$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
\begin{eqnarray*}
LHS(k+1) = LHS(k) + \frac{1}{(k+1)^2}
\end{eqnarray*}
Since P(k) is true, we find:\\
\begin{eqnarray*}
LHS(k+1) < 2 - \frac{1}{k} + \frac{1}{(k+1)^2}
\end{eqnarray*}
Since $k+1 > k$,  $\displaystyle\frac{1}{(k+1)^2} < \displaystyle\frac{1}{k(k+1)}$.\\
Therefore
\begin{eqnarray*}
LHS(k+1) < 2 - \frac{1}{k} + \frac{1}{k(k+1)}
\end{eqnarray*}
We can use the property : $\displaystyle \frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$:
\begin{eqnarray*}
LHS(k+1) & <&  2 - \frac{1}{k} + \frac{1}{k}  -\frac{1}{k+1} \\
LHS(k+1) &<& 2 -\frac{1}{k+1}
\end{eqnarray*}
Since $RHS(k+1) = 2-\displaystyle\frac{1}{k+1}$, we get $LHS(k+1) < RHS(k+1)$ which validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n>1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4} 

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

\vspace{0.2in}
Let $P(n)$ be the proposition: $n^2-7n+12\geq 0$. We want to show that $P(n)$ is true for $n$ greater than 3. Let us define $LHS(n)= n^2-7n+12$.
\\
Notice that $LHS(1)=6$,  $LHS(2)=2$  and $LHS(3)=0$ hence $P(1)$, $P(2)$ and $P(3)$ are true.
\begin{itemize}
\item \emph{Basis step:} $P(4)$ is true:
\begin{eqnarray*}
LHS(4) = 4^2 -7\ast4 + 12 = 0
\end{eqnarray*}
Therefore $LHS(4) \geq 0$ and $P(4)$ is true.

\item \emph{Inductive step:} Let $k$ be a positive integer greater than 3 ($k> 3$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.

\begin{eqnarray*}
LHS(k+1) &=& (k+1)^{2} - 7(k+1) + 12 \\
&=& k^{2} + 2k + 1 - 7k - 7 + 12\\
&=& (k^{2} - 7k + 12) + (2k - 6)
\end{eqnarray*}

Since $P(k)$ is true, we know that $k^{2} - 7k + 12 \geq 0$. Since $k \geq 4$,
$2k - 6 > 0$. Therefore, $(k+1)^{2} - 7(k+1) + 12 > 0$.\\
This validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n>3$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5} 

\textcolor{blue}{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.}

\vspace{0.2in}
Let $P(n)$ be the proposition: A set $S_n$ with $n$ elements has $\displaystyle\frac{n(n-1)}{2}$ subsets that contain exactly two elements.\\
We want to show that $P(n)$ is true for all $n\geq 2$; we use a proof by induction.
\begin{itemize}
\item \emph{Basis step:} $P(2)$ is true: As the set $S_2$ contains 2 elements, there is only one subset that containing exactly two elements, and $n(n-1)/2 = 1$.\\

\item \emph{Inductive step:} Let $k$ be a positive integer greater or equal to 2 ($k\geq 2$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let us consider a set $S_{k+1}$ of $k+1$ elements: 
$S_{k+1}= \{ a_1, a_2,\ldots, a_k, a_{k+1} \}$. 
Let $S_k$ be the set with the first $k$ elements of $S_{k+1}$: 
$S_k= \{ a_1, \ldots, a_k \}$. Since $P(k)$ is true,  
there are $k(k-1)/2$ subsets of $S_k$ that contain exactly two elements. \\
The $(k+1)$th element of $S_{k+1}$ $a_{k+1}$ can pair with each of the elements of $S_k$
to build a subset of $S_{k+1}$ of exactly two elements. These new 
subsets do not duplicate with any of the $k(k-1)/2$ subsets of $S_k$ because the
$(k+1)$th element does not appear in any of these subsets. There are
no other two-element subsets. \\
Therefore, the total number of two-element
subsets of $S_{k+1}$ is: $k(k-1)/2 + k = (k(k-1)+2k)/2 = k(k+1)/2 = 
(k+1)((k+1)-1)/2$.
This validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n\geq 2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6} 

\textcolor{blue}{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:}
\textcolor{blue}{
\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$.}

\vspace{0.2in}
This is again a case in which if we are not careful, we can prove nearly every thing!
In the proof given:
\begin{itemize}
\item the basis step is correct: by definition we indeed have $a^0=1$.

\item Inductive step: the assumption should really be written: \\
assume that $a^j=1$, for all integers $j$ with $0 \leq j \leq k$.
When we write $a^{k+1}=\frac{a^ka^k}{a^{k-1}}$, we need to use the premise for $j=k$ and $j=k-1$.
But for $k=0$, $k-1<0$, and we are outside the limit of validity. 
This means that we can show $P(k)\rightarrow P(k+1)$ only for $k>0$. This is not enough to apply the method of proof by induction!
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 7} 

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

\vspace{0.2in}
Let $P(n)$ be the proposition: 21 divides $4^{n+1}+5^{2n-1}$.
We want to show that $P(n)$ is true for all $n$; we use a proof by induction.
\begin{itemize}
\item \emph{Basis step:} $P(1)$ is true: when $n=1$, $4^{n+1}+5^{2n-1} = 16 + 5 = 21$ is divisible by 21.\\
\item \emph{Inductive step:} Let $k$ be a positive integer, and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
\begin{eqnarray*}
4^{(k+1)+1}+5^{2(k+1)-1} &=& 4\ast4^{k+1} + 5^2\ast5^{2k-1}\\
&=& 4\ast4^{k+1} + 25\ast5^{2k-1}\\
&=& 4(4^{k+1}+5^{2k-1}) + 21\ast5^{2k-1}
\end{eqnarray*}

 Because $4^{k+1}+5^{2k-1}$ and $21\ast5^{2k-1}$ both are divisible by 21, $4^{(k+1)+1}+5^{2(k+1)-1}$ is also divisible by 21:
$P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n\geq 0$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 8} 

\textcolor{blue}{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.}

\vspace{0.2in}
Let $P(n)$ be the proposition: $f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$ \\
where $f_n$ are the Fibonacci numbers. Let us define $LHS(n)=f_1^2+f_2^2+\ldots+f_n^2$ and
$RHS(n)=f_nf_{n+1}$.

We want to show that $P(n)$ is true for all $n$; we use a proof by induction.
\begin{itemize}
\item \emph{Basis step:} $P(1)$ is true: 
\begin{eqnarray*}
LHS(2) &=& f^{2}_{1} = 1^2 = 1 \\
RHS(2) &=& f_{1}f_{2} = 1.
\end{eqnarray*}
\item \emph{Inductive step:} Let $k$ be a positive integer, and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Then
\begin{eqnarray*}
LHS(k+1) &=& f^{2}_{1} + f^{2}_{2} + ... + f^{2}_{k} + f^{2}_{k+1} \\
&=& f_{k}f_{k+1} + f^{2}_{k+1}\\
&=& f_{k+1}(f_{k} + f_{k+1})\\
&=& f_{k+1}f_{k+2}
\end{eqnarray*}
and
\begin{eqnarray*}
RHS(k+1) = f_{k+1}f_{k+2}
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$,  which validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 9} 

\textcolor{blue}{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.}

\vspace{0.2in}
Let $P(n)$ be the proposition: $f_0-f_1+f_2-\ldots-f_{2n-1}+f_{2n}=f_{2n-1}-1$ \\
where $f_n$ are the Fibonacci numbers. Let us define $LHS(n)=f_0-f_1+f_2-\ldots-f_{2n-1}+f_{2n}$ and
$RHS(n)=f_{2n-1}-1$.

We want to show that $P(n)$ is true for all $n>0$; we use a proof by induction.
\begin{itemize}
\item \emph{Basis step:} 
\begin{eqnarray*}
LHS(1) = f_0-f_1+f_2 = 0 -1 + 1 = 0 \\
RHS(1) = f_1 - 1 = 1 - 1 = 0
\end{eqnarray*}
Therefore $LHS(1)=RHS(1)$ and $P(1)$ is true.
\\
\item \emph{Inductive step:} Let $k$ be a positive integer, and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Then
\begin{eqnarray*}
LHS(k+1) &=& f_0 - f_1 + ... - f_{2k-1} + f_{2k} - f_{2k+1} + f_{2k+2} \\
&=& f_{2k-1} - 1 - f_{2k+1} + f_{2k+2}\\
&=& f_{2k-1} - 1 - f_{2k+1} + (f_{2k} + f_{2k+1})\\
&=& f_{2k-1} + f_{2k} - 1\\
&=& f_{2k+1} - 1
\end{eqnarray*}
and
\begin{eqnarray*}
RHS(k+1) = f_{2k+1} -1
\end{eqnarray*}
Therefore $LHS(k+1)=RHS(k+1)$, which validates that $P(k+1)$ is true.
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Extra Credit} 

\textcolor{blue}{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.}

\vspace{0.2in}
Let $P(n)$ be the proposition: A set $S_n$ with n elements has $\displaystyle\frac{n(n-1)(n-2)}{6}$ subsets that contain exactly three elements.\\
We want to show that $P(n)$ is true for all $n\geq 3$; we use a proof by induction.
\begin{itemize}
\item \emph{Basis step:} $P(3)$ is true:  In a set $S_3$ of 3 elements, there is only one subset that containing exactly three elements, and $(3(3-1)(3-2))/6 = 1$.\\
\item \emph{Inductive step:} Let $k$ be a positive integer greater or equal to 3 ($k\geq 3$), and let us suppose that $P(k)$ is true.
We want to show that $P(k+1)$ is true.\\
Let $S_{k+1}=\left\{a_1,a_2,\ldots,a_{k+1}\right\}$ be a set of $k+1$ elements, and let $S_k$ be its subset $S_k=\left\{a_1,a_2,\ldots,a_{k}\right\}$. \\
$S_k$ contains k elements: since $P(k)$ is true, it contains $k(k-1)(k-2)/6$ three-element subsets.
In addition, based on exercise 7, it also contains $k(k-1)/2$ two-element subsets.\\
The subsets of $S_{k+1}$ that contain 3 elements are the subsets of 3 elements of $S_k$, plus the subsets of 3 elements containing $a_{k+1}$.\\
$a_{k+1}$ can pair with each of the two-element subsets of $S_k$ in order to form a subset
of exact three elements of $S_{k+1}$. These new subsets do not duplicate with any of 
the other three-element subsets because $a_(k+1)$ does not appear in any of these subsets. 
There are no other three-element subsets. \\
Therefore, the total number $N_3$ of three-element 
subsets of $S_{k+1}$ is:
\begin{eqnarray*}
 N_3 &=& \frac{k(k-1)(k-2)}{6} + \frac{k(k-1)}{2} \\
 &=& \frac{k(k-1)[(k-2)+3]}{6} \\
 & =& \frac{(k+1)k(k-1)}{6} \\
 &=& \frac{(k+1)((k+1)-1)((k+1)-2)}{6}
 \end{eqnarray*}
This validates that $P(k+1)$ is true.\\
\end{itemize}
The principle of proof by mathematical induction allows us to conclude that $P(n)$ is true for all $n\geq 2$.

\end{document}