%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\pagestyle{plain}
\setcounter{secnumdepth}{0}
\usepackage{amsmath}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{graphicx}
\usepackage{amsfonts}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{TCIstyle=LaTeX article (bright).cst}
%TCIDATA{CSTFile=article.cst}
%TCIDATA{Created=Thu Jan 20 19:11:37 2000}
%TCIDATA{LastRevised=Wed May 17 08:40:35 2000}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Exams and Syllabi\Assignment">}
%TCIDATA{Language=Portuguese (Continental)}
\setlength{\topmargin}{-1.0in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textwidth}{6.5in}
\def\labelenumi{\arabic{enumi}.}
\def\theenumi{\arabic{enumi}}
\def\labelenumii{(\alph{enumii})}
\def\theenumii{\alph{enumii}}
\def\p@enumii{\theenumi.}
\def\labelenumiii{\arabic{enumiii}.}
\def\theenumiii{\arabic{enumiii}}
\def\p@enumiii{(\theenumi)(\theenumii)}
\def\labelenumiv{\arabic{enumiv}.}
\def\theenumiv{\arabic{enumiv}}
\def\p@enumiv{\p@enumiii.\theenumiii}
\parindent=0pt

\usepackage{babel}
\makeatother
\begin{document}
\begin{center}\textbf{Análise de Algoritmos}\end{center}

\begin{center}\textbf{Lista de Exerc\'{\i}cio 1}\end{center}

\begin{enumerate}
\item Encontre a função geradora para a sequência $\left\langle 0,0,4,4,4,...\right\rangle $.
\item Encontre a função geradora para a sequência $\left\langle 0,0,0,3,6,12,24,...\right\rangle $.
\item Encontre a sequência cuja função geradora é $F(z)=(z+6)^{2}$.
\item Encontre a sequência cuja função geradora é $F(z)=z^{3}+z^{4}+e^{2z}$.
\item Encontre a sequência cuja função geradora é $F(z)=3/(1+4z)^{3}-2/(5-1z)$.
\item Encontre a função geradora para a recorrência


\begin{eqnarray*}
T_{0} & = & 0\\
T_{1} & = & 1\\
T_{n} & = & 10T_{n-1}-16T_{n-2}\text{ \,\,\,\,\,\, se }n>1.\end{eqnarray*}


Determine a fórmula fechada para o $n$-ésimo coeficiente.

\item Encontre a função geradora para a recorrência


\begin{eqnarray*}
T_{0} & = & 0\\
T_{1} & = & 1\\
T_{2} & = & 2\\
T_{n} & = & 6T_{n-1}-11T_{n-2}+6T_{n-3}\text{ \,\,\,\,\,\, se\,}n>2.\end{eqnarray*}


Determine a fórmula fechada para o $n$-ésimo coeficiente.

\item Encontre a função geradora para a recorrência


\begin{eqnarray*}
T_{0} & = & 0\\
T_{n} & = & 2T_{n-1}+n+2^{n} \,\,\,\,\,\,\textrm{se}\, n>0.\end{eqnarray*}


Determine a fórmula fechada para o $n$-ésimo coeficiente.

\item Encontre a função geradora para a recorrência


\begin{eqnarray*}
T_{0} & = & 0\\
T_{n} & = & T_{n-1}+n^{2} \,\,\,\,\,\,\textrm{se\,}n>0.\end{eqnarray*}


Determine a fórmula fechada para o $n$-ésimo coeficiente.

\item Encontre a funções geradoras e as fórmulas fechadas para os $n$-ésimos
coeficientes para as recorrências alinhadas:


\begin{eqnarray*}
A_{n} & = & A_{n-1}+B_{n-1}+C_{n-1}\\
B_{n} & = & 4^{n}-C_{n-1}\\
C_{n} & = & 4^{n}-B_{n-1},\end{eqnarray*}


com $n\geq1$ e $A_{0}=B_{0}=C_{0}=1$.

\item Encontre a função geradora para a recorrência


\begin{eqnarray*}
(n+1)T_{n+1} & = & (n+r)T_{n} \,\,\,\,\,\,\textrm{se}\, n\geq0.\end{eqnarray*}


Determine a fórmula fechada para o $n$-ésimo coeficiente. Assuma
que $r$ é uma cons\-tante.\end{enumerate}

\end{document}
