Expanding to find patterns and make hypotheses
Last class we learned what a recurrence relation is, how it
defines a sequence, how we can immeditely translate a recurrence
relation to a recursive function in a program, what a closed
form is, and how we can use induction to *prove* that some
proposed closed form really is correct for the
function defined by a given recurrence relation.
What we didn't cover is how to derive good guesses (it sounds
better to say "hypotheses") for closed forms to a given
recurrence relation. Now we will address that!
Consider the function $a(\cdot)$ defined by the following
recurrence relation:
$$
\begin{array}{l}
a(n) = a(n-1) + n + 1\\
a(0) = 2
\end{array}
$$
What we went through in class (and I summarize here) is
expanding the recurrence relation, looking for a
pattern.
$$
\begin{array}{rcl}
a(n) &=& \underbrace{{\color{red}{a(n-1)}}}_{a(n-2) + (n-1) + 1} + n + 1\\
&=& {\color{red}{a(n-2) + (n-1) + 1}} + n + 1\\
&=& a(n-2) + n + (n-1) + 1 + 1\\
&=& \underbrace{{\color{red}{a(n-2)}}}_{a(n-3) + (n-2) + 1} + n + (n-1) + 1 + 1\\
&=& {\color{red}{a(n-3) + (n-2) + 1}} + n + (n-1) + 1 + 1\\
&=& a(n-3) + n + (n-1) + (n-2) + 1 + 1 + 1\\
&=& a(n-{\color{red}{3}}) +
\underbrace{n + (n-1) + (n-2)}_{{\color{red}{\text{3 terms}}}} +
\underbrace{1 + 1 + 1}_{{\color{red}{\text{3 terms}}}}\\
&&\vdots\\
&=& a(n-{\color{red}{k}}) +
\underbrace{n + (n-1) + \cdots + (n-(k-1))}_{{\color{red}{\text{k terms}}}} +
\underbrace{1 + 1 + \cdots + 1}_{{\color{red}{\text{k terms}}}}\\
&&\vdots\\
&=&
\underbrace{a(n-{\color{red}{n}})}_{a(0) = 2} +
\underbrace{n + (n-1) + \cdots + 2 + 1}_{{\color{red}{\text{n terms}}}} +
\underbrace{1 + 1 + \cdots + 1}_{{\color{red}{\text{n terms}}}}\\
&=& 2\ +\ 1+2+\cdots+n\ + \ n
\end{array}
$$
We found a pattern and we imagined continuing the expanding
process until the end - i.e. we get to $f(0)$. And now we
have a hypothesis:
hypothesis:
$a(n) = 1+2+\cdots+n\ + \ n + 2$
We can calculate a few terms in the series based on the
recurrence, and check the formula and it seems to work. But, of
course, we need to
prove that it, in fact, always works.
For function $a(\cdot)$ defined by the recurrence relation
above,
$a(n) = 1+2+\cdots+n\ + \ n + 2$.
we will prove this by induction on $n$.
base case $n=0$:
According to the recurrence relation, $a(0) = 2$.
At zero, the closed form expression is $1+2+\cdots+n\ + \ n + 2 = 0 + 0 + 2 = 2.
✓
inductive case $n > 0$:
$$
\begin{array}{rcl}
a(n) &=& a(n-1) + n + 1 \text{, by the inductive hypothesis }
a(n-1) = 1+2+\cdots + (n-1) + (n-1) + 2\\
&=& 1 + 2 + \cdots + (n-1) + (n-1) + 2 + n + 1\\
&=& 1 + 2 + \cdots + n + n + 2
\end{array}
$$
So $a(n) = 1+2+\cdots+n\ + \ n + 2$
as required. ✓
ACTIVITY
Your job in class was to expand the following two recurrence
relations, find the pattern and make a hypothesis. Then, of
course, give an inductive proof that your hypotheses were
correct.
- $f(n) = f(n-1) + 3,\ f(0) = 5$
- $g(n) = 2\cdot g(n-1),\ g(0) = 3$
Gauss's proof
In the first example, we showed that
$a(n) = 1+2+\cdots+n\ + \ n + 2$. But this isn't really
a closed form, because of the "$1+2+\cdots+n$".
So let us see how to get a closed form for this sum.
There is a beautiful derivation and proof that is said to have
been discovered by the famous mathematician Carl Fredrich Gauss
as a child. Let us call the sum $S_n$. In other words
$S_n = 1 + 2 + \cdots + n$.
$$
\begin{array}{rccccccccc}
S_n = &1 &+& 2 &+ &\cdots &+ &(n-1) &+& n\\
S_n = &n &+& (n-1) &+& \cdots &+& 2 &+& 1\\
\hline
2\cdot S_n = & n(n+1)\\
%S_n =& \frac{n(n+1)}{2}
\end{array}
$$
... and so $S_n =\frac{n(n+1)}{2}$.
It's beautiful, isn't it?