\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{7}{October 31, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart
Let $s_n$ be the number of such sequences. A string ending in $n$ must
consist of a string ending in something less than $n$, followed by an
$n$ as the last term. Therefore the recurrence relation is
$s_n=s_{n-1}+s_{n-2}+\ldots +s_2+s_1$. Here is another approach, with
a more compact form of the answer. A sequence ending in $n$ is either
a sequence ending in $n-1$, followed by $n$ (and there are clearly
$s_{n-1}$ of these), or else it does not contain $n-1$ as a term at
all, in which case it is {\em identical} to a sequence ending in $n-1$
in which the $n-1$ has been replaced by an $n$ (and clearly there are
$s_{n-1}$ of these as well). Therefore $s_n=2s_{n-1}$. Finally we notice
that we can derive the second form from the first (or vice versa)
algebraically (for example, $s_4=2s_3=s_3+s_3=s_3+s_2+s_2=s_3+s_2+s_1$).
\ppart We need two initial conditions if we use the second formulation 
above, $s_1=1$ and $s_2=1$ (otherwise, our argument is invalid, because the 
first and last terms are the same). There is one sequence ending in $1$,
namely the sequence with just this $1$ in it, and there is only the 
sequence $1,2$ ending in $2$. If we use the first formulation above,
then we can get by with just the initial condition $s_1=1$.
\ppart Clearly the solution to this recurrence relation and initial 
condition is $s_n=2^{n-2}$ for all $n\geq 2$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Using the Akra-Bazzi generalization of the master theorem, we have
that for $T$, $k=1, a_1 = 7, b_1 =1/2, g(n) = n^2$ and for $T'$,
$k=1, a_1 = a, b_1 =1/4, g(n) = n^2$.  In both cases, $g'(n) = 2n$
which is polynomially bounded.  In the first case (for $T$), we have that
$7\cdot(1/2)^p = 1$ or that $p = \log_2 7$.  In the second case (for
$T'$), we have that $a \cdot (1/4)^p = 1$ or that $a \cdot (1/2)^{2p}
= 1$, or that $p = \frac{1}{2} \log_2 a$.  This gives
%
$$T(n) = \Theta(n^{\log_2 7} (1+ \int_1^n \frac{u^2}{u^{\log_2 7 + 1}} du)) =
\Theta(n^{\log_2 7})$$
and 
$$T'(n) = \Theta(n^{(\log_2 a)/2} (1+ \int_1^n \frac{u^2}{u^{(\log_2
a)/2 + 1}} du)) = \Theta(n^{(\log_2 a)/2} (1 + \int_1^n u^{1- (\log_2
a)/2} du)),$$
so that if $(\log_2 a)/2 > 2$, we have that $T'(n) = \Theta(n^{(\log_2
a)/2})$ and if $(\log_2 a)/2 = 2$, we have that $T'(n) = \Theta(n^{(\log_2
a)/2} \log n) = \Theta(n^2 \log n)$ and if $(\log_2 a)/2 < 2$, we have that $T'(n) = \Theta(n^2)$.  

This means that for $A'$ to be asymptotically faster than $A$, we need to have
$\frac{1}{2} \log_2 a < \log_2 7$, or that $a < 7^2$, so that the
largest integer value of $a$ is $48$.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Note that $\Theta(\log_a n) = \Theta(\log_b n)$, so we will leave out
the bases for the logarithms when we are using asymtotic notation.

\bparts

\ppart 
$a_1 = 3$, $b_1 = 1/3$, $h_1(n) = \lfloor n/3 \rfloor - n/3$, $g(n) =
n$, $p = 1$,
%
$$T(n) = \Theta(n(1+ \int_1^n \frac{u}{u^2} du)) = \Theta(n \log n).$$

\ppart
$a_1 = 4$, $b_1 = 1/3$, $h_1(n) = \lfloor n/3 \rfloor - n/3$, $g(n) =
n^2$, $p = \log_3 4$,
%
$$T(n) = \Theta(n^{\log_3 4}(1+ \int_1^n \frac{u^2}{u^{\log_3 4 + 1}} du)) =
\Theta(n^{\log_3 4}(1+ \int_1^n u^{1 - \log_3 4} du)) = \Theta(n^2).$$

\ppart
$a_1 = 3$, $b_1 = 1/4$, $h_1(n) = \lfloor n/4 \rfloor - n/4$, $g(n) =
n$, $p = \frac{1}{2} \log_2 3$,
%
$$T(n) = \Theta(n^{(\log_2 3)/2}(1+ \int_1^n \frac{u}{u^{(\log_2 3)/2 +
1}} du)) = \Theta(n^{(\log_2 3)/2}(1+ \int_1^n u^{- (\log_2 3)/2} du)) 
= \Theta(n).$$

\ppart
$a_1 = 1$, $a_2 = 1$, $b_1 = 1/4$, $b_2 = 1/3$, $h_1(n) = \lfloor n/4
\rfloor - n/4$, $h_2(n) = \lfloor n/3 \rfloor - n/3$, $g(n) = n$, $p
= 0.5605$ (the exact value does not matter, it turns out that for this case, we only need to know that $p < 1$),
%
$$T(n) = \Theta(n^p(1+ \int_1^n \frac{u}{u^{p+1}} du)) =
\Theta(n^p(1+ \int_1^n u^{-p} du)) = \Theta(n).$$ 

\ppart
$a_1 = 1$, $a_2 = 1$, $b_1 = 1/4$, $b_2 = 3/4$, $h_1(n) = \lceil n/4
\rceil - n/4$, $h_2(n) = \lfloor 3n/4 \rfloor - 3n/4$, $g(n) = n$, $p
= 1$,
%
$$T(n) = \Theta(n(1+ \int_1^n \frac{u}{u^2} du)) =
\Theta(n \log n).$$

\ppart
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = 0$, $g(n) = \sqrt{n}$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{\sqrt{u}}{u^{3/2}} du)) =
\Theta(n^{1/2} \log n).$$

\ppart
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = 1$, $g(n) = \sqrt{n}$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{\sqrt{u}}{u^{3/2}} du)) =
\Theta(n^{1/2} \log n).$$

\ppart
$a_1 = 2$, $b_1 = 1/4$, $h_1(n) = \sqrt{n}$, $g(n) = 1$, $p = 1/2$,
%
$$T(n) = \Theta(n^{1/2}(1+ \int_1^n \frac{1}{u^{3/2}} du)) =
\Theta(n^{1/2}).$$

\ppart
Write $n = 3^m$ and $S(m) = T(3^m)$.  Then the recurrence becomes
%
$$S(m) = 3S(\frac{m}{3}) + m,$$
%
for which $a_1 = 3$, $b_1 = 1/3$, $h_1(m) = 0$, $g(m) = m$, $p = 1$,
%
$$S(m) = \Theta(m(1+ \int_1^m \frac{u}{u^2}du)) = \Theta(m \log m),$$
%
so that
%
$$T(n) = S(\log n) = \Theta(\log n \log \log n).$$

\ppart
Write $n = e^m$ and $S(m) = T(e^m)$.  Then the recurrence becomes
%
$$S(m) = \sqrt{e} S(\frac{m}{e}) + m,$$
%
for which $a_1 = \sqrt{e}$, $b_1 = 1/e$, $h_1(m) = 0$, $g(m) = m$, $p = 1/2$,
%
$$S(m) = \Theta(m^{1/2}(1+ \int_1^m \frac{u}{u^{3/2}}du)) = \Theta(m),$$
%
so that
%
$$T(n) = S(\log n) = \Theta(\log n).$$

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

All logarithms in this question are base $2$.  We will present exact
solutions to both recurrences below.  The claims were obtained by
``plug-and-chug''.  Only the inductive proof will be shown below.  
We will let $c_1$ and $c_2$ be constants such that $c_1 \leq T(n) \leq
c_2$ for $n \leq 2$. 

\bparts

\ppart
We claim that $\lceil \log \log n \rceil + c_1 \leq T(n) \leq \lceil
\log \log n \rceil + c_2$, for $n \leq 2$.  This can be proven by
induction.   The base
case follows immediately, since $\log \log n = 0$ for $n \leq 2$.  
For $n > 2$, we have $T(n) = T(\sqrt{n}) + 1 \geq
\lceil \log \log \sqrt{n} \rceil + c_1 + 1$ by
inductive hypothesis.  This simplifies to $T(n) \geq \lceil \log
 (\frac{1}{2} \log n) \rceil + c_1 + 1 = \lceil \log 1/2 + \log \log n
\rceil + c_1 +
1 = \lceil \log \log n - 1 \rceil + c_1 + 1 = \lceil \log \log n \rceil
+ c_1$.  On the other side, we have $T(n) = T(\sqrt{n}) + 1 \leq
\lceil \log \log \sqrt{n} \rceil + c_2 + 1$ by
inductive hypothesis.  This simplifies to $T(n) \leq \lceil \log
(\frac{1}{2} 
\log n) \rceil + c_2 + 1 = \lceil \log 1/2 + \log \log n \rceil +
c_2 + 1 = \lceil \log \log n - 1 \rceil + c_2 + 1 = \lceil \log \log n
\rceil + c_2$ , completing the induction.  

So $T(n) = \Theta(\log \log n)$ is asymptotically tight.

\ppart
We claim that $n \lceil \log \log n \rceil + c_1 n^{1 - 2^{- \lceil
\log \log n \rceil}} \leq T(n) \leq n \lceil \log \log n \rceil + c_2
n^{1 - 2^{- \lceil \log \log n \rceil}}$.
This can be proven by induction.  For the base case, we can easily
verify that our claim implies that $c_1 \leq T(n) \leq c_2$, since $\lceil
\log \log n \rceil = 0$, which is true by the definition of $c_1$ and $c_2$.

For $n > 2$, we have that $T(n) = \sqrt{n} T(\sqrt{n}) + n$ which is
at least $\sqrt{n} [\sqrt{n} \lceil \log \log \sqrt{n} \rceil + c_1
(\sqrt{n})^{1 - 2^{- \lceil \log \log \sqrt{n} \rceil}}] + n$ by inductive
hypothesis.  Simplifying gives us
%
\begin{eqnarray*}
T(n) & \geq & \sqrt{n} [\sqrt{n} \lceil \log \log n - 1 \rceil + c_1
n^{(\frac{1}{2})(1 - 2^{- \lceil \log \log n - 1 \rceil})}] + n \\
& = & n \lceil \log \log n \rceil - n + c_1 n^{\frac{1}{2} + \frac{1}{2}
- 2^{- \lceil \log \log n - 1 \rceil - 1}} + n \\
& = & n \lceil \log \log n \rceil + c_1 n^{1 - 2^{- \lceil \log \log n
\rceil}}.
\end{eqnarray*}
%
The other side is essentially the same.  This time, we have that $T(n) \leq
\sqrt{n} [\sqrt{n} \lceil \log \log \sqrt{n} \rceil + c_2
(\sqrt{n})^{1 - 2^{- \lceil \log \log \sqrt{n} \rceil}}] + n$ by
inductive hypothesis.  Simplifying gives us
%
\begin{eqnarray*}
T(n) & \leq & \sqrt{n} [\sqrt{n} \lceil \log \log n - 1 \rceil + c_2
n^{(\frac{1}{2})(1 - 2^{- \lceil \log \log n - 1 \rceil})}] + n \\
& = & n \lceil \log \log n \rceil - n + c_2 n^{\frac{1}{2} +
\frac{1}{2}
- 2^{- \lceil \log \log n - 1 \rceil - 1}} + n \\
& = & n \lceil \log \log n \rceil + c_2 n^{1 - 2^{- \lceil \log \log n
\rceil}},
\end{eqnarray*}
completing the induction.  The asymptotically tight bounds are therefore 
$T(n) = \Theta(n \log \log n)$.  

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

$T(n)-(n-1)T(n-1) = \displaystyle \sum_{i=1}^{n-2}{iT(i)} = T(n-1)~
\Longrightarrow ~ T(n) = (n-1)T(n-1)+T(n-1) \Longrightarrow T(n)=nT(n-1)$. 

$T(1)=1, ~T(2)=1\cdot T(1)=1,~\mbox{and}~~T(3)=2\cdot T(2)+1\cdot T(1)=3$.  
So we have:
\[
T(n) = \left\{ \begin{array}{ll}
       1   & \mbox{for $n=1$}\\
      n!/2 & \mbox{for $n\geq 2$}
                \end{array}
        \right. 
\]
Verify by induction:
\begin{proof}
Base Case: $n=2 \Longrightarrow T(2)=\sum_{i=1}^1{iT(i)}=1\cdot T(1)=1=2!/2$.

Inductive Step: 
\begin{eqnarray*}
T(n+1) &=& (n+1)T(n)\\
       &=& (n+1)~n!/2 ~~~~~\mbox{by the induction hypothesis}\\
       &=& (n+1)!/2
\end{eqnarray*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

First solve the general solution of the homogeneous recurrence:
$T(n)=4T(n-1)-4T(n-2)$. Its characteristic equation is:
$\alpha^2-4\alpha+4=0 \Longrightarrow (\alpha-2)^2=0 \Longrightarrow~ 2$ 
is a root
with multiplicity $2$.  Solutions are all linear combinations of $2^n$ and 
$n2^n$, i.e. $A2^n+Bn2^n$ for $A, B\in \reals$. 
Find any particular solution to the nonhomogeneous recurrence (ignoring
initial conditions). For a polynomial ``drive'', try polynomial of 
equal degree (higher if $1$ is a root of characteristic equation).
Guess $T(n)=an^2+bn+c$, and solve for $a,b$, and $c$ satisfying 
the recurrence:
\begin{eqnarray*}
an^2+bn+c &=& 4(a(n-1)^2 + b(n-1) + c)-4(a(n-2)^2 + b(n-2) + c)+n^2\\
          &=& 4((n-1)^2 - (n-2)^2)+4b((n-1)- (n-2))+4c(1-1) + n^2\\
          &=& 4a(2n-3) + 4b + n^2 \\
          &=& n^2 + 8an + 4b - 12c
\end{eqnarray*}
which implies that $a=1,~ b=8a=8,~ c=4b-12a=32-12=20$.

So general solution to inhomogeneous recurrence is $A2^n+Bn2^n+n^2+8n+20$ for 
$A, B\in \reals$. 

Find values for $A, B$ meeting initial conditions:

$0=T(0)=A+20 \Longrightarrow A=-20$.

$1=T(1)=2A+2B+1+8+20=2B-40+29 \Longrightarrow B=1+40-29=12 
\Longrightarrow B=6$.

Solution: $T(n)=(6n-20)2^n+n^2+8n+20$.

Check answers for small values of $n$ (to avoid arithmetic and algebraic
errors):

$T(0)=-20+20=0$

$T(1)=-14\cdot 2+1+8+20=-28+29=1$

$T(2)=-8\cdot 4+4+16+20=-32+40=8=4\cdot 1-4\cdot 0+2^2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart
$f(3) = f(2)+f(1)+2^1=5$

$f(4)=f(3)+f(2)+2^2=11$

$f(5)=f(4)+f(3)+2^3=11+5+8=24$

\ppart $f(n)=f(n-1)+f(n-2)+2^{n-2}$
\ppart Solve homogeneous recurrence: It is just the Fibonacci recurrence, 
where roots are ${1+\sqrt{5}}\over{2}$ and ${1-\sqrt{5}}\over{2}$ (of course
we could solve the characteristic polynomial as well).

Find particular solution: for exponential ``drive'', try exponential with
same base. 

Guess $f(n)=A2^n \Longrightarrow A2^n=A2^{n-1}+A2^{n-2}+2^{n-2}
\Longrightarrow 4A-2A-A=1 \Longrightarrow A=1$.

General solution to recurrence is 
$f(n)=B({{1+\sqrt{5}}\over{2}})+C({{1-\sqrt{5}}\over{2}}) + 2^n$, for 
$B, C\in \reals$.

Solve for $B$ and $C$ meeting initial conditions:

$0=f(0)=B+C+1 \Longrightarrow C=-(B+1)$.

$1=f(1)=B({{1+\sqrt{5}}\over{2}})+C({{1-\sqrt{5}}\over{2}}) + 2=
B({{1+\sqrt{5}}\over{2}})-(B+1)({{1-\sqrt{5}}\over{2}}) + 2=
B(\sqrt{5})-{{1-\sqrt{5}}\over{2}} + 2 \Longrightarrow 
B={1\over{\sqrt{5}}}(-1+{{1-\sqrt{5}}\over{2}})=
{-1\over{\sqrt{5}}}({{1+\sqrt{5}}\over{2}})$,~~ and 

$C=-(B+1)={{1-\sqrt{5}}\over{2\sqrt{5}}}={1\over{\sqrt{5}}}({{1-\sqrt{5}}\over{2}})$.

So: 
\begin{eqnarray*}
f(n) &=& 2^n - {1\over{\sqrt{5}}}({{1+\sqrt{5}}\over{2}})^{n+1} + {1\over{\sqrt{5}}}({{1-\sqrt{5}}\over{2}})^{n+1}\\
     &=& 2^n - ({1\over{\sqrt{5}}}({{1+\sqrt{5}}\over{2}})^{n+1} - {1\over{\sqrt{5}}}({{1-\sqrt{5}}\over{2}})^{n+1})\\
     &=& 2^n - F_{n+1}, ~~~~\mbox{where~~$F_{n+1}$~~ is the ${n+1}^{st}$ Fibonacci number}.
\end{eqnarray*}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}





