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

\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}


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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Review problems\\[2ex] 
       \rm\normalsize ECS 17 (Winter 2026)}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Simple propositions} 

For each proposition on the left, indicate if it is a tautology or not:

\begin{table}[!hbt]
        \begin{threeparttable}
        \caption{Propositional logic}
        \label{table:logic}
                \begin{tabular}{L{7cm} C{7cm}}
                \hline 
                Proposition & Tautology (Yes/ No) \\
                \hline 
                \\
                $(\lnot (p \land q) ) \leftrightarrow (\lnot p \lor \lnot q)$ & \\ \\
                $(\lnot (p \land q) ) \leftrightarrow (\lnot p \land \lnot q)$ & \\ \\
                $(\lnot (p \lor q) ) \leftrightarrow (\lnot p \land \lnot q)$ & \\ \\
                if $6^2 = 36$ then $2=3$ & \\ \\
                if $6^2 = -1$ then $36 = -1$ & \\ \\
                \hline
                 \end{tabular}
	         \end{threeparttable}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Knights and Knaves} 

A very special island is inhabited only by Knights and Knaves. Knights always tell the truth, while Knaves always lie. You meet three inhabitants: Alex, John and Sally. Alex says, ``If John is a Knight then Sally is a Knight". John says, ``Alex is a Knight and Sally is a Knave". Can you find what Alex, John, and Sally are? Explain your answer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proofs: direct, indirect, and contradictions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Different methods of proofs}

Let $n$ be an integer. Show that if $3n^2 + 2n + 9$ is odd, then $n$ is even using a direct, indirect, and proof by contradiction.

\subsection{Proof by contradiction}

Let $n$ be a strictly positive integer. Show that $\frac{2n+1}{2n+4}$ is not an integer

\subsection{Proof by contradiction}

Let $n$ be a strictly positive integer. Show that if $\sqrt{n^2+1}$ is not an integer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proofs by induction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Identity}

\noindent a) Show that $1 + 3 + \ldots 2n -1 = n^2$, for all $n\ge 1$.

\noindent b) Show that $\displaystyle \sum_{k=1}^{n} \frac{1}{4k^2-1} = \frac{n}{2n+1}$ for all integer $n\ge 1$.

\subsection{Multiples}
\emph {For the next two problems, we say that an integer $n$ is a multiple of an integer $m$ if and only if there exist an integer $k$ such that $n=km$.}

\vspace{0.1in}

\noindent a) Show that $ (7^n-2^n)$ is a multiple of 5  for all integer $n\ge 1$.

\noindent b) Show that $ n(2n+1)(7n+1) $ is a multiple of 6 or all integer $n \ge 1$.

\subsection{Stamps: 1}

Use induction to prove that any postage of $n$ cents (with $n\ge 30$) can be formed using    
only 6--cent and 7--cent stamps.

\subsection{Stamps: 2}

Use induction to prove that any postage of $n$ cents (with $n\ge 18$) can be formed using    
only 3--cent and 10--cent stamps.

\subsection{Other}

Prove by induction that for all $n\ge1$, there exist two strictly positive integers $a_n$ and $b_n$ such that
$(1+\sqrt{2})^n = a_n + b_n \sqrt{2}$.

\subsection{Fibonacci}

Let $f_n$ be the Fibonacci numbers. show that $f_{n-1}f_{n+1} - f_n^2 = (-1)^n$, for all $n>1$.

\end{document}