%hw2.tex: Homework assignment 2
%%a Plain TeX file by Doron Zeilberger

%begin macros
\nopagenumbers
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros

\centerline
{
\bf Dr. Z.'s Number Theory Homework assignment 2
}




{\bf 1.} For the following (i) Guess  a nice formula by inspection (ii) Give a rigorous proof of your
guessed formula, using the Fundamental Theorem of Discrete Calculus (iii) Give a fully rigorous
Zeilberger-style proof.


{\bf a.}
$$
\sum_{i=1}^{n} 3i-1 \quad ,
$$

{\bf b.}
$$
\sum_{i=1}^{n} (2i-1)^2 \quad ,
$$

{\bf c.}
$$
\sum_{i=1}^{n} (2i-1)^3 \quad .
$$

{\bf 2.} Prove the following identities 
(i) using the Fundamental Theorem of Discrete Calculus (ii) using a Zeilberger-style proof via checking special cases.


{\bf a.}
$$
\sum_{i=1}^{n} i^3 = \left ( \frac{n(n+1)}{2} \right )^2 \quad .
$$

{\bf b.}
$$
\sum_{i=1}^{n} i(i+1)(i+2) = \frac{1}{4} n(n+1)(n+2)(n+3) \quad .
$$


{\bf 3.}  Use the Fundamental Theorem of Discrete Calculus  to prove

{\bf a.} 
$$
\sum_{i=1}^{n} q^i = \frac{q(1-q^{n})}{1-q} \quad ,
$$
for any number $q$, and any positive integer $n$ .

{\bf b.} 
$$
\sum_{i=1}^{n} i q^i = 
{\frac {n{q}^{n+2}-n{q}^{n+1}-{q}^{n+1}+q}{ \left( q-
1 \right) ^{2}}}
$$
for any number $q$, and any positive integer $n$ .


{\bf 4.} In a small Italian village there are 100 married couples, 
except for the priest (so  there are 100 married men and 100 married women, and one priest). One Sunday,
the priest announces in Church:

  It came to my knowledge that {\bf at least} one woman is unfaithful. It is a great sin to shoot your
cheating wife unless you are {\bf completely} sure that she is cheating on you. On the other hand,
if you are sure, by all means, you should shoot her exactly at {\bf midnight} (after you found out
for sure).

 Of course, due to gossip, everyone knows about everybody else's wife, {\bf but not} about one's own wife.

For the first 99 midnights, nothing happened, but at the 100th midnight, there were heard
$100$ shots, meaning that all the husbands knew for sure that their wives were cheating on them.
Use mathematical induction to explain this.

\end
