\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ciência da Computação
\hfill ICEx/UFMG \\
{\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \\
\underline{Terceira Prova} \hfill 30/10/2013

\vspace*{5mm}
\noindent Cada uma das 5 questões a seguir vale 3 pontos.
\vspace*{1mm}
\begin{enumerate}
 \item \label{q1} Um certo banco paga 6\% de juros ao ano para um certo tipo de aplicação. Além disso, ele paga um bônus
       de 10\% do investimento inicial ao final de cada ano (após computados os juros). Encontre uma relação de recorrência
			 para o saldo após decorridos $n$ anos, se não houver nenhum saque, e se o investimento inicial for de R\$ $k$.

 \item Seja $a_n$ o número de maneiras de dispor $n$ bandeirinhas lado a lado, podendo cada bandei\-ri\-nha ser de uma
       das cores: verde, amarelo ou azul. Determine uma relação de recorrência para $a_n$, supondo que
			 \emph{bandeirinhas adjacentes não podem ser ambas amarelas}.

 \item \label{q5} Resolva a relação de recorrência:
       \begin{quote}
			   $a_0=0$, $a_1=3$; \\
			   $a_n= a_{n-1}+2a_{n-2}$ para $n\geq 2$.
			 \end{quote}

 \item Resolva a relação de recorrência:
       \begin{quote}
			   $a_0=0$, $a_1=3$; \\
			   $a_n= a_{n-1}+2a_{n-2} + 4.3^n$ para $n\geq 2$.
			 \end{quote}

 \item De quantas maneiras podemos permutar os 10 dígitos decimais de forma que nenhum dígito ímpar fique em sua
       posição natural? Considere que a posição natural de 0 é 0, a posição natural de 1 é 1, a posição natural de 2 é 2,
			 e assim por diante. Por exemplo, o arranjo 0563912748 só tem em suas posições naturais os dígitos 0, 3 e 7.
\end{enumerate}

\vspace*{3mm}
\noindent Cada uma das 3 questões a seguir vale 1 ponto (são 2 pontos extra).

\begin{enumerate}
 \item[6.] Seja novamente $a_n$ o número de maneiras de dispor $n$ bandeirinhas lado a lado, podendo cada
       bandeirinha ser de uma das cores: verde, amarelo ou azul. Determine uma relação de recorrência para $a_n$,
			 supondo agora que \emph{bandeirinhas adjacentes não podem ter a mesma cor}.

 \item[7.] Resolva a relação de recorrência obtida na questão \ref{q1}.

 \item[8.] Quantos arranjos existem das letras AAAOOOXX em que não apareçam 3 letras conse\-cu\-tivas idênticas?

\end{enumerate}


\hrule
\vspace*{.5mm}
\hrule

\vspace*{3mm}
No verso estão algumas informações úteis para resolução de equações de recorrência.

\pagebreak
\begin{flushleft}\it
Algumas informações úteis para resolução de equações de recorrência:
\end{flushleft}

\begin{itemize}
 \item Se uma equação característica tem uma raiz $\alpha_i$ de multiplicidade $m$, então ela contribue com $m$
       soluções: $\alpha_i^n$, $n\alpha_i^n$, $n^2\alpha_i^n$, \ldots, $n^{m-1}\alpha_i^n$.
 \item Se $g(n)$ é a solução geral para a parte homogênea de uma relação de recorrência cuja parte não homogênea é $f(n)$,
       então $g(n)+p(n)$ é a solução geral para a parte recorrente. Para se obter $p(n)$:
			 \begin{itemize}
        \item se $f(n)$ é polinômio de ordem $n$, $p(n)$ é um polinômio de ordem $n$ somado com a
              multiplicidade de 1 na equação caraterística;
        \item se $f(n)$ é da forma $\alpha^n$, $p(n)$ é da forma $An^k\alpha^n$, para algum $A$,
              sendo $k$ a multiplicidade de $\alpha$ na equação característica.
       \end{itemize}
 \item A solução para uma relação da recorrência da forma 
       \begin{quote}
			  $a_0=C$; \\
			  $a_n=h(n)a_{n-1}+f(n)$ para $n\geq 1$;
			 \end{quote}
			 é $u_nv_n$, sendo a relação de recorrência para $u_n$:
			 \begin{quote}
        $u_0=1$; \\
			  $u_n=h(n)a_{n-1}$ para $n\geq 1$;
			 \end{quote}
			 e para $v_n$:
			 \begin{quote}
        $v_0=a_0$; \\
			  $v_n=v_{n-1}+f(n)/u_n$ para $n\geq 1$.
       \end{quote}
\end{itemize}
\end{document}
 