
  
%hoC.tex: 
%%a Plain TeX file by Doron Zeilberger for March 10, 2006 Colloq.

%\bigskip & \bigskip \cr
%&
%\cr
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end macros
 

\centerline
{
\bf Dr. Z's March 10 Colloquium Handout
}

{\bf Problem Type}: A function is given by some rule.
First conjecture, and then rigorously prove, an explicit
formula for it.


%%General Problem


{\bf Example Problem}: Let $f_L(n)$ be the expected life
of a gambler in a fair casino, who currently has $n$ dollars
and loses or wins a dollar with probability $1/2$, and has
to quit when he is ruined, or when he has $L$ dollars.
Find an explicit formula for $f_L(n)$ as a function of
$n$ and $L$.

%%Specific Problem


\bigskip
\hrule
\bigskip
%\halign{#\hfill  & \quad #\hfill \cr
\halign{           
\vtop{\hsize=15pc\noindent #\strut} \qquad
&
\vtop{\hsize=15pc\noindent #\strut} \cr
{\bf Steps} & {\bf Example} \cr  &  \cr
{\bf 1.} 
%%%General Step 1
Using human (or computer) ingenuity, set up an
algorithm for computing the function numerically
for ``small values'' of the arguments.

%%%End General Step 1
&
%%%Specific Step 1
{\bf 1.} 
For a fixed $L$, the $n+1$ quantities $f_L(n)$ ($n=0 \dots L$)
are completely characterized by the system of $n+1$ 
linear equations with $n+1$  unknowns
$$
f_L(n)={{1} \over {2}} f_L(n-1)+
{{1} \over {2}} f_L(n+1)+1 \quad , \quad ( 1 \leq n \leq L-1)
$$
$$
f_0(0)=0 \quad, \quad f_L(L)=L \quad .
$$



%%%End Specific Step 1
\cr
\bigskip & \bigskip \cr
{\bf 2.} 
%%% General Step 2
Using a linear solver, crank out enough data.
%%% End General Step 2
&
{\bf 2.} 
%%%Specific Step 2
$$
f_3(0)=0, f_3(1)=2, f_3(2)=2, f_3(3)=0 \quad ,
$$
$$
f_4(0)=0, f_4(1)=3, f_4(2)=4, f_4(3)=3, f_4(4)=0 \quad ,
$$
$$
f_5(0)=0, f_5(1)=4, f_5(2)=6, f_5(3)=6, f_5(4)=4, f_5(5)=0 \quad .
$$ 
%%%End Specific Step 2

\cr \bigskip & \bigskip \cr

{\bf 3.} 
%%% General Step 3
Conjecture an {\it ansatz} and use 
{\it undetermined coefficients} to find it
(if possible).

%%% End General Step 3
&
{\bf 3.} 
%%% Specific Step 3
Setting $f_L(n)=an^2+bn^2+cn$ and solving for $a,b,c$
(for each specific $L$) we get
$$
f_3(n)=n(3-n) \quad f_4(n)=n(4-n) \quad f_5(n)=n(5-n) 
$$
$$
\quad f_6(n)=n(6-n)  \quad, \quad f_7(n)=n(7-n)  \quad.
$$
%%% End Specific Step 3

\cr
\bigskip & \bigskip \cr
{\bf 4.} 
%%% General Step 4
Using the same methodology conjecture an expression in $L$
for $f_L(n)$, then prove it {\it rigorously} by 
using the {\it definining algorithm},
but now {\bf symbolically}.
%%% End General Step 4
&
{\bf 4.} 
%%%Specific Step 4
$$
f_L(n)=n(L-n) \quad .
$$
Now let's prove it! Let's denote \hfill\break
$g_L(n):=n(L-n)$. We have
$$
g_L(n)-{{1} \over {2}} g_L(n-1)- {{1} \over {2}} g_L(n+1)-1 =
$$
$$
L(n-L)-{{1} \over {2}} (n-1)(L-(n-1))- {{1} \over {2}} (n+1)(L-(n+1))-1 =0 
\quad .
$$
Also $g_L(0)=0 \cdot (L-0)=0$ and $g_L(L)=L(L-L)=0$.
So we have a {\bf rigorous} proof that $f_L(n)=g_L(n)$ for
{\it every} $n$ and $L$.
%%%End Specific Step 4

\cr \bigskip & \bigskip \cr



\cr}



\end





