\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,ulem}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math 303}{Homework 13}{Due: Wed. Apr 24, 2024}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\newcommand{\PS}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\st}{\colon \,}
\newcommand{\comp}[1]{\overline{#1}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{theorem}{Theorem}{}


\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  Unless the problem indicates otherwise, all problems require some justification; a correct answer without supporting reasoning is not sufficient.  Submissions must be stapled.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}
\item Prove the following using induction or a ``no smallest counterexample'' argument.
\begin{enumerate}
	\item For each $n\in\NN$, we have $\displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$.
	\item For each $n\in\NN$, we have $\displaystyle \sum_{k=1}^n \frac{k}{(k+1)!} = 1 - \frac{1}{(n+1)!}$.
\end{enumerate}


\item Use induction to prove the following.
\begin{enumerate}
	\item For each $n\in\NN$, we have $\sum_{i=1}^n (8i-5) = 4n^2 - n$.
	\item For each non-negative integer $n$, we have $9\mid 4^{3n} + 8$.
	\item If $n\in\NN$, then $2^n + 3^n \le 5^n$.
	\item If $n\in\NN$, then $( \sum_{k=1}^n k )^2 = \sum_{j=1}^n j^3$.
	\item If $n\in\NN$, then $\sum_{k=1}^n k\binom{n}{k} = n2^{n-1}$.  (Hint: you may need one to use one of our identities involving binomial coefficients.)
\end{enumerate}

\item Using any method, prove the following.
\begin{enumerate}
	\item If $x_1, \ldots, x_n$ are non-negative real numbers, then 
	\[(1+x_1)(1+x_2)\cdots(1+x_n) \ge 1 + x_1 + x_2 + \cdots + x_n.\]
	\item If $n\in\ZZ$, then $\gcd(3n+5,5n+8)=1$.
	\item If $n$ is a non-negative integer, then $(1+\sqrt{2})^n + (1-\sqrt{2})^n$ is an even integer.
\end{enumerate}

\item Recall the Fibonacci numbers, defined by $F_1 = 1$, $F_2 = 1$, and $F_k = F_{k-1} + F_{k-2}$ for $k\ge 2$.  Prove that each integer $n$ can be represented as the sum of Fibonacci numbers, no two of which are consecutive.  (For example, $2 = F_3$, $10 = F_6 + F_3 = 8 + 2$, and $20 = F_7 + F_5 + F_3 = 13 + 5 + 2$.  However, even though $20 = F_7 + F_5 + F_2 + F_1$, this is not a desired representation for $20$ since it uses the consecutive Fibonacci numbers $F_1$ and $F_2$.)

\end{enumerate}
\end{document}
