%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Tue Apr 29 13:21:22 2003}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=Lab Report.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{AllPages=
%F=36,\PARA{038<p type="texpara" tag="Body Text" >\hfill \thepage}
%}


\input{tcilatex}
\begin{document}


\subsection{\protect\vspace{1pt}A Derivation of the Explicit Formula for the
Fibonacci Sequence and a Generalization of the Fibonacci Sequence}

\vspace{1pt}

\vspace{1pt}Let \ \ $f_{m}(x)=\left( 1-\sum_{k=1}^{m}x^{k}\right)
\sum_{n=0}^{\infty }a_{n}x^{n}=a_{0}+\sum_{n=1}^{m-1}\left(
a_{n}-\sum_{k=1}^{n}a_{n-k}\right) x^{n}+\sum_{n=m}^{\infty }\left(
a_{n}-\sum_{k=1}^{m}a_{n-k}\right) x^{n}$

Now if $f_{m}(x)\equiv 1$ , then we obtain the ''generalized'' Fibonacci
sequence:

$a_{0}=1;a_{n}=\sum_{k=1}^{n}a_{n-k}$ \ for \ $1\leq n\leq
m-1;a_{n}=\sum_{k=1}^{m}a_{n-k}$ \ for \ $n\geq m$

\vspace{1pt}with the ''generating function'' , $g_{m}\left( x\right) =\frac{1%
}{1-\sum_{k=1}^{m}x^{k}}=\sum_{n=0}^{\infty }a_{n}x^{n}$

This can also be expressed as $g_{m}\left( x\right) =\frac{1}{%
1-\sum_{k=1}^{m}x^{k}}=\frac{1}{1-x\frac{1-x^{m}}{1-x}}$ $=$ $\frac{1-x}{%
1-2x+x^{m+1}}$

\vspace{1pt}

Special Cases: $m=1;a_{n}=1$ for \ $n\geq 0$ \ and \ $g_{_{1}}\left(
x\right) =\sum_{n=0}^{\infty }x^{n}=\frac{1}{1-x}$ is the geometric series.

\vspace{1pt}

$m=2;a_{0}=a_{1}=1$ and $a_{n}=a_{n-1}+a_{n-2}$ \ for \ $n\geq 2$ \ and \ $%
g_{_{2}}\left( x\right) =\sum_{n=0}^{\infty }a_{n}x^{n}=\frac{1}{1-x-x^{2}}=%
\frac{-1}{\left( x-(\frac{-1+\sqrt{5}}{2})\right) \left( x-(\frac{-1-\sqrt{5}%
}{2})\right) }=$ $\frac{-1}{\left( x+(\frac{1-\sqrt{5}}{2})\right) \left( x+(%
\frac{1+\sqrt{5}}{2})\right) }$

\vspace{1pt}$=\frac{c}{\left( x+(\frac{1-\sqrt{5}}{2})\right) }+\frac{d}{%
\left( x+(\frac{1+\sqrt{5}}{2})\right) }\Longrightarrow -1=c\left( x+(\frac{%
1+\sqrt{5}}{2})\right) +d\left( x+(\frac{1-\sqrt{5}}{2})\right) =\allowbreak
x(c+d)+\frac{1}{2}(c+d)+\frac{1}{2}(c-d)\sqrt{5}=0x-1\Longrightarrow c=-d$ \
and \ $c\sqrt{5}=-1$

$c=\frac{-1}{\sqrt{5}}$ and $d=\frac{1}{\sqrt{5}}$, so

\vspace{1pt}$g_{_{2}}\left( x\right) =\sum_{n=0}^{\infty }a_{n}x^{n}=\frac{1%
}{1-x-x^{2}}=\frac{1}{\sqrt{5}}\left( \frac{1}{\left( x+(\frac{1+\sqrt{5}}{2}%
)\right) }-\frac{1}{\left( x+(\frac{1-\sqrt{5}}{2})\right) }\right) $

$=\frac{1}{\sqrt{5}}\left( \frac{1}{(\frac{\sqrt{5}+1}{2})\left( 1+\frac{x}{(%
\frac{\sqrt{5}+1}{2})}\right) }+\frac{1}{(\frac{\sqrt{5}-1}{2})\left( 1-%
\frac{x}{(\frac{\sqrt{5}-1}{2})}\right) }\right) $

for $|x|<\frac{\sqrt{5}-1}{2}=\frac{2}{\sqrt{5}+1}=\frac{1}{\text{''golden
mean''}}$ the two terms can be expanded using the geometric series:

\vspace{1pt}$g_{_{2}}\left( x\right) =\sum_{n=0}^{\infty }a_{n}x^{n}=\frac{1%
}{\sqrt{5}}\left( \frac{1}{(\frac{\sqrt{5}+1}{2})}\sum_{k=0}^{\infty }\left( 
\frac{-x}{(\frac{\sqrt{5}+1}{2})}\right) ^{k}+\frac{1}{(\frac{\sqrt{5}-1}{2})%
}\sum_{k=0}^{\infty }\left( \frac{x}{(\frac{\sqrt{5}-1}{2})}\right)
^{k}\right) $

$=\sum_{n=0}^{\infty }\frac{x^{n}}{\sqrt{5}}\left( \frac{\left( -1\right)
^{n}}{\left( \frac{\sqrt{5}+1}{2}\right) ^{n+1}}+\frac{1}{\left( \frac{\sqrt{%
5}-1}{2}\right) ^{n+1}}\right) $ \ So the Fibonacci number $a_{n}$ defined
by the recurrance with $a_{0}=a_{1}=1$ and $a_{n}=a_{n-1}+a_{n-2}$ \ for $%
n>1 $ is given by the following explcit formula:

\vspace{1pt}

\vspace{1pt}$a_{n}=\frac{1}{\sqrt{5}}\left( \frac{\left( -1\right) ^{n}}{%
\left( \frac{\sqrt{5}+1}{2}\right) ^{n+1}}+\frac{1}{\left( \frac{\sqrt{5}-1}{%
2}\right) ^{n+1}}\right) =\frac{1}{\sqrt{5}}\left( \left( \frac{2\left( 
\sqrt{5}+1\right) }{5-1}\right) ^{^{n+1}}+\left( -1\right) ^{n}\left( \frac{%
2\left( \sqrt{5}-1\right) }{5-1}\right) ^{^{n+1}}\right) $

$=\frac{1}{\sqrt{5}}\left( \left( \frac{\sqrt{5}+1}{2}\right)
^{^{n+1}}+\left( -1\right) ^{n}\left( \frac{\sqrt{5}-1}{2}\right)
^{^{n+1}}\right) =\frac{1}{\sqrt{5}}\left( \frac{\sqrt{5}+1}{2}\right)
^{^{n+1}}\left( 1+\left( -1\right) ^{n}\left( \frac{\sqrt{5}-1}{\sqrt{5}+1}%
\right) ^{^{n+1}}\right) $.

It is clear that asymptotically $a_{n}\rightarrow \frac{1}{\sqrt{5}}\left( 
\frac{\sqrt{5}+1}{2}\right) ^{^{n+1}}$for large $n$. For example, for

$\vspace{1pt}$

$n=11,$ $a_{11}=144,$ while $\frac{1}{\sqrt{5}}\left( \frac{\sqrt{5}+1}{2}%
\right) ^{12}=\allowbreak 144.\,\allowbreak 001\,388\,875\,\allowbreak
493\,228\,224\,\allowbreak 375\,392$

\paragraph{Convergence: \ $r_{n}=\frac{a_{n}}{a_{n-1}}=1+\frac{1}{r_{n-1}}+%
\frac{1}{r_{n-1}r_{n-2}}+...+\frac{1}{r_{n-1}r_{n-2\cdots }r_{n-m}}$}

Assuming that $r_{n}$ converges (I can show this for $m=1$(EASY) and $m=2$
(not so hard))

this leads to the equation $h_{m}(r)=r^{m}-r^{m-1}-r^{m-2}-...-1=r^{m}-\frac{%
r^{m}-1}{r-1}=0$

$h_{m}(0)=-1;$ $h_{m}(1)=1-m;$ $h_{m}(2)=1;$ $h_{m}\left( r\right) $ has
only one sign change so it has only one positive root which must be between $%
1$ and $2.$ Thus, $\sum_{n=0}^{\infty }a_{n}x^{n}$ has a radius of
convergence between $\frac{1}{2}$ and $1.$

\end{document}
