\documentclass[11pt]{article}

\usepackage{times,mathptm}
\usepackage{pifont}
\usepackage{exscale}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{epsfig}

\textwidth 6.5in
\textheight 9in
\oddsidemargin -0.0in
\topmargin -0.0in

\parindent 0pt     % How much the first word of a paragraph is indented. 
\parskip 0pt	   % How much extra space to leave between paragraphs.

\begin{document}

\begin{center}             % If you only centering 1 line use \centerline{}
\begin{LARGE}
{\bf CSci 243 Homework 6}
\end{LARGE}
\vskip 0.25cm      % vertical skip (0.25 cm)

**My name**  %update me!!
\end{center}


\begin{enumerate}

\item (10 points) 
\begin{enumerate}
\item (4 points)  Find the formula for $\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \ldots + \frac{1}{n\cdot (n+1)}$ using telescoping.
\item (6 points) Prove the formula you found is true by induction.
\end{enumerate}

\item (10 points) Prove by induction that for $n\geq8$, $n^22^n \leq n!$.

\item (10 points) Prove that 21 divides $4^{n+1} + 5^{2n-1}$ when $n$ is a positive integer using induction.


\item (10 points) Use strong induction to prove that any positive integer $n$ can be written as a sum of distinct powers of two, that is, as a sum of subset of integers $2^0=1$, $2^1=2, 2^2=4$, and so on. [Hint: consider two cases.]

\item (5 points) Find the flaw with the following proof that $a^n=1$ for all nonnegative integers $n$ and all nonzero real numbers $a$.

{\bf Basis step:} $a^0=1$ is true.

{\bf Inductive step:} Assume that $a^j=1$ for all nonnegative integer $j\le k$. Consider the case of $k+1$.
$$a^{k+1}=\frac{a^k\cdot a^k}{a^{k-1}}=\frac{1\cdot 1}{1}=1.$$

\item (5 points) Find the flaw with the following proof that every postage of 3 cents or more can be formed using just 3-cent and 4-cent stamps.

{\bf Basis step:} We can form postage of 3 cents with a single 3-cent stamp and we can form postage of 4 cents using a single 4-cent stamp.

{\bf Inductive step:} Assume that we can form postage of $j$ cents for all integers $j$ with $3\le j\le k$ using just 3-cent and 4-cent stamps. We can then form postage of $k+1$ cents by replacing one 3-cent stamp with a 4-cent stamp or by replacing two 4-cent stamps with three 3-cent stamps.

\end{enumerate}

\end{document}
