\documentclass[12pt, reqno]{amsart}

\textwidth=7in
\textheight=9.5in
\topmargin=0in
\headheight=0in
\headsep=.5in
\hoffset=-.85in

\begin{document}

\title[Math 250 Handout 5 - Induction]{Math 250 Handout 5 - Induction}\maketitle

\begin{enumerate}

\item Prove that for any integer $n\geq 1$, $$2^0 +2^1 +...+2^{n-1} =2^{n}-1.$$

\item Prove that for any integer $n \geq 1$, $n^2$ is the sum of the first n odd integers. (For example, $3^2 =1+3+5$.)

\item Show that $7^n - 1$ is divisible by 6 for all integers $n \geq 0$.

% \item Prove that $n^5 - 5n^3 + 4n$ is divisible by 120 for all integers $n \geq 1$.

\item Prove that $$n^9 - 6n^7 + 9n^5 - 4n^3$$ is divisible by 8640 for all integers n $\geq$ 1.

% \item Prove that $$n^2 \mid ((n+1)^n -1)$$ for all integers n $\geq$ 1.

% \item Show that $$(x-y)\mid (x^n -y^n)$$ for all integers $n \geq 1$.

% \item Use the result of the previous problem to show that for all integers $n \geq 1$
% \[
% 8767^{2345} - 8101^{2345
% }\]
% is divisible by $666$.

\item Show that 
\[
2903^n - 803^n - 464^n + 261^n
\]
is divisible by $1897$ for all integers $n \geq 1$.

\item Prove that if $n$ is an even natural number, then the number $13^n + 6$ is divisible by 7.

% \item Prove that for every $n \in \mathbf{Z}_{\geq 2}$, $n^3 - n$ is a multiple of 6.

\item Prove that $n! \geq 3^n$ for all integers $n \geq 7$.

\item Prove that $2^n \geq n^2$ for all integers $n \geq 4$.

\item Consider the sequence defined by $a_1 = 1$ and $a_n = \sqrt{2 a_{n-1}}$. Prove that $a_n <$ 2 for all integers $n \geq 1$.

% \item Prove that the equation $x^2 + y^2 = z^n$ has a solution in positive integers $x, y, z$ for all integers $n \geq 1$.

% \item Prove that $n^3 +(n+1)^3 +(n+2)^3$ is divisible by 3 for all integers $n \geq 1$. 

\item (Challenge problem) Prove that 
\[
\frac{1}{n + 1} + \frac{1}{n +2} + \cdots + \frac{1}{3n+1} > 1 
\]
for all integers $n \geq 1$.

\item Prove that 
\[
\frac{4^n}{n+1} \leq \frac{(2n)!}{(n!)^2}
\]
for all integers $n \geq 1$. 

\item Consider the Fibonacci sequence $\{F_n\}$ defined by $F_0 = 0, F_1 = 1, F_{n+1} = F_n + F_{n-1}, n \geq 1$. Prove that each of the following statements is true for all integers $n \geq 1$. 

 \begin{itemize}
 \item [(a)] $F_1 +F_3 +F_5 +...+F_{2n-1} =F_{2n}$
 \item [(b)] $F_2 +F_4 +F_6 +...+F_{2n} =F_{2n+1} -1$
 \item [(c)] $F_n< 2^n$
 \item [(d)] $F_{n-1} F_{n+1} = F^2_n + (-1)^{n+1}$.
 \item [(e)] Let $\alpha = \frac{1 + \sqrt{5}}{2}$ and $\beta = \frac{1 - \sqrt{5}}{2}$. Prove that $F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}$. (Hint: first prove by, for example, direct calculation that $\alpha$ and $\beta$ are solutions of the equation $x^2 - x - 1 = 0$.)
 \item [(f)] Prove that $F_1^2 + \cdots + F_n^2 = F_nF_{n+1}$.\vspace{0.3cm}
 \item [(g)] Find a formula for $F_1 + \cdots + F_n$ and prove it via induction.\vspace{0.3cm}
% \item F_{n+1} = sum F_i

% prove sum (n-i)F_i = F_{n+1}
 \end{itemize}

\item Prove that $n! > 2^n$ for all integers $n \geq 4$.
% \item Prove that the expression $3^{3n+3} - 26n - 27$ is a multiple of 169 for all positive integers $n$.

\newpage
\item Prove that if $k$ is odd, then $2^{n+2}$ divides 
\[
k^{2^n} -1
\] 
for all positive integers $n$.



\item Let $a_n$ be the sequence defined by $a_1 := 1$, $a_n := na_{n-1}$. Prove that $a_n = n!$.\vspace{0.3cm}
\item Let $a_n$ be the sequence defined by $a_1 := 2$, $a_n := 2a_{n-1}$. Prove that $a_n = 2^n$.\vspace{0.3cm}
\item Prove that $3^n$ is odd for every non-negative integer.\vspace{0.3cm}
\item Prove that $n(n-1)$ is even for every positive integer $n$.\vspace{0.3cm}
\item Prove that $n^3 + 2n$ is a multiple of 3 for every positive integer $n$.\vspace{0.3cm}
\item Prove that, for all $n > 1$, $\frac{1}{1\cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{(n-1)n} = \frac{n-1}{n}$\vspace{0.3cm}
\item Prove that $1^2 + 4^2 + 7^2 + \cdots + (3n-2)^2 = \frac{1}{2}n(6n^2 - 3n - 1)$ for $n \in \mathbf{Z}_{\geq 1}$.\vspace{0.3cm}
\item Prove that $2^2 + 5^2 + 8^2 + \cdots + (3n-1)^2 = \frac{1}{2}n(6n^2 + 3n - 1)$ for $n \in \mathbf{Z}_{\geq 1}$.\vspace{0.3cm}
\item Prove that $1^3 + 2^3 + 3^3 + \cdots + n^3 = (1 + 2 + 3 + \cdots + n)^2$ (Hint: use $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$.)\vspace{0.3cm}
\item Let $n \in \mathbf{Z}_{\geq 0}$. Prove that $\displaystyle{\sum}_{i = 1}^n i = \frac{n(n+1)}{2}$.\vspace{0.3cm}
% \item Let $n \in \mathbf{Z}_{\geq 0}$. Prove that $\displaystyle{\sum}_{i = 1}^n
% (2i-1) = n^2$.\vspace{0.3cm}
\item Let $n \in \mathbf{Z}_{\geq 0}$. Prove that $\displaystyle{\sum}_{i = 1}^n i^2 = \frac{n(n+1)(2n+1) }{6}$. \vspace{0.3cm}
\item Let $n \in \mathbf{Z}_{\geq 0}$. Prove that $\displaystyle{\sum}_{i = 1}^n i^3 = \frac{n^2(n+1)^2}{4}$.\vspace{0.3cm}
\item Let $n \in \mathbf{Z}_{\geq 0}$. Find a formula for $\displaystyle{\sum}_{i = 1}^n i^4$. Prove that your formula is correct. 
\vspace{0.3cm}

\item Prove that $2^n > n^2$ for $n \geq 5$ for $n \in \mathbf{Z}_{\geq 1}$.\vspace{0.5cm}

% In the following problems, let ${n \choose k} = \frac{n!}{(n-k)!k!}$.
% \vspace{0.3cm}
% \item Let $x$ and $y$ be variables. Prove that 
% \[
% (x + y)^n = \sum_{k = 0}^n {n \choose k} x^{n-k}y^k.
% \]\vspace{0.3cm}
% \item Prove that 
% \[
%  {n \choose k} = {n - 1 \choose k} - {n - 1 \choose k-1}.
% \]

% % \newpage
% % \textbf{Lucas numbers}. Read the wikipedia page about Lucas
% % numbers. Try to prove a few of the statements. \textbf{Rewrite this problem.}

\end{enumerate}
\end{document}

