%p2S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf Solutions to 
Attendance Quiz \# 2 for Dr. Z.'s Number Theory
}
\bigskip

{\bf 1.} 
(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.

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

{\bf Sol.}: (i) The (correct) guess is $S(n)=(n-1)n(n+1)/3$.
 Defining 
$$
S(n):=\sum_{i=1}^{n} i(i-1) \quad,
$$
The {\bf summand} is of degree $2$ so the sum $S(n)$ is of degree $3$ in n, so that general
{\bf template} is $a_0+a_1n+a_2n^2+a_3n^3$, so we need four data points.
we first {\bf collect data}
$$
S(0)=0 \quad, \quad
S(1)=1 \cdot 0= 0 \quad, \quad
S(2)=1 \cdot 0 +2 \cdot 1= 2 \quad, \quad
S(3)=1 \cdot 0 +2 \cdot 1 +3 \cdot 2= 8 \quad.
$$

But since $S(0)=0$ $a_0=0$, so it is divisible by $n$, and since $S(1)=0$, the polynomial is also divisible by $n-1$.
Hence a more efficient template is
$$
S(n)=n(n-1)(c_0+c_1n) \quad
$$

Since $S(2)=2$ we have
$$
2=S(2)=2(2-1)(c_0+2c_1) \quad
$$

Since $S(3)=8$ we have
$$
8=S(3)=3(3-1)(c_0+3c_1) \quad
$$
We have two equations for the two unknowns $c_0$ and $c_1$
$$
c_0+2c_1=1 \quad, \quad
c_0+3c_1=\frac{4}{3} \quad .
$$
Solving, we get $c_0=\frac{1}{3}$ and $c_1=\frac{1}{3}$.

Hence $S(n)=n(n-1)(\frac{1}{3}+ \frac{1}{3}n)$.

The conjecture is
$$
\sum_{i=1}^{n} i(i-1) \, = \, \frac{(n-1)n(n+1)}{3}  \quad.
$$

(ii)  Here  $S(n)=(n-1)n(n+1)/3$ and $a(n)=(n-1)n$.
First we checn that $S(0)=0$ (true). Next:
$$
S(n)-S(n-1)=(n-1)n(n+1)/3-(n-2)(n-1)n/3=
(n-1)n/3 \cdot ((n+1)-(n-2))=((n-1)n/3) \cdot (3) 
= (n-1)n \quad =a(n).
$$
{\bf QED.}
(by the Fundamental Theorem of Discrete Calculus).

(iii) The {\bf degree} of the right side is $3$, so it
is enough to check the identity
$$
\sum_{i=1}^{n}= \frac{(n-1)n(n+1)}{3} \quad
$$
for $3+1=4$ different values. Of course, the
simplest are $n=0,1,2,3$.

$n=0$: $0=(0-1)0/3$  is true

$n=1$: $(1-1)(1)=(1-1)(1)(1+1)/3$  is true

$n=2$: $(1-1)(1)+ (2-1)(2) =(2-1)(2)(2+1)/3$  is true

$n=3$: $(1-1)(1)+ (2-1)(2)+ (3-1)(3) =(3-1)(3)(4)/3$  is true.

{\bf QED!}.



{\bf 2.} Prove the following identity
(i) using the Fundamental Theorem of Discrete Calculus 
(ii) using a Zeilberger-style proof via checking special cases.
$$
\sum_{i=1}^{n} \, i^2 = \frac{n(n+1)(2n+1)}{6} \quad .
$$

{\bf Sol. of 2.} Here $a(i)=i^2$ and $S(n)=n(n+1)(2n+1)/6$.
First let's make sure that $S(0)=0$ (true!).

Next:
$$
S(n)-S(n-1)=
 \frac{n(n+1)(2n+1)}{6} - \frac{(n-1)(n-1+1)(2(n-1)+1)}{6} 
$$
$$
= \frac{n(n+1)(2n+1)}{6} - \frac{(n-1)(n)(2n-1))}{6} 
$$
$$
=\frac{n}{6} ( (n+1)(2n+1) - (n-1)(2n-1)) =
\frac{n}{6} ( 2n^2+3n+1 - (2n^2-3n+1)) =
\frac{n}{6} ( 6n) = n^2 =a(n)\quad . QED.
$$
The formula follows from
the Fundamental Theorem of Discrete Calculus.

(ii) The degree of the polynomial (in $n$)
that appears up on the
right side is $3$ so 
in order to give a fully rigorous proof that the
identity is true for {\bf all} positive integers $n$,
we only need to check 
it for $3+1=4$ special cases. Of course,
the simplest are $n=0,1,2,3$.

$n=0$: empty sum is $0$ and $S(0)=0(1)(1)/6=0$. ok!

$n=1$: sum is $1^2=1$ and $S(1)=1(2)(3)/6=1$. ok !

$n=2$: sum is $1^2+2^2=1+4=5$ and $S(2)=2(3)(5)/6=5$. ok !

$n=3$: sum is $1^2+2^2+3^2=1+4+9=14$ and 
$S(3)=3(4)(7)/6=14$. ok ! 

{\bf QED!}


\end




