\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial6}{Problems for Tutorial 6}{October 28, 1996}

\section {Master Theorem}

Use the Akra-Bazzi method to obtain asymptotic bounds for the recurrence \\
$T(n) = aT(bn) + n^{\alpha}$ \\
where $a > 0$ and $0 < b < 1$.

\section {Akra-Bazzi for difference equations}

Consider the linear difference equation \\
$f(n) = \sum_{i=1}^d a_{i}f(n-i) + g(n)$ \\
where $a_i > 0, \forall i$.
\begin{itemize}

\item Find a transformation $n \rightarrow m$ that will convert this problem into a recurrence of the form \\
$T(n) = \sum_{i=1}^d a_{i}T(b_{i}n) + G(n)$

\item show how $p$ can be obtained.  Is $p$ unique?  Discuss your conjectures.

\item Apply your results to obtain bounds for the solution of the difference equation \\
$f(n) = f(n-1) + 2f(n-2) +n2^{n}$
 
\end{itemize}

\end{document}
