
\problemdata     
{S01-PS5-5}           
{recurrences, induction, plug-and-chug}              
{F98-PS5, S01-PS5} 		
{S01 Karger}


\begin{problem}


Consider the following recurrence.
\begin{eqnarray*}
y_0 & = & 1 \\ y_n & = & \sum_{i=1}^n y_{n-i} \cdot 2^i
\end{eqnarray*}

\begin{problemparts}

\problempart Guess the solution to the recurrence. \hint Look at the first few terms

\solution {

First, we compute the first few terms to form the basis for a guess.

\begin{eqnarray*}
y_0 & = &   1 \\
y_1 & = &   2 \cdot y_0
     =  2 \cdot 1
     =  2 \\
y_2 & = &   2 \cdot y_1 + 4 \cdot y_0
     =  2 \cdot 2 + 4 \cdot 1
     =  8 \\
y_3 & = &   2 \cdot y_2 + 4 \cdot y_1 + 8 \cdot y_0
     =  2 \cdot 8 + 4 \cdot 2 + 8 \cdot 1
     =  32 \\
y_4 & = &   2 \cdot y_3 + 4 \cdot y_2 + 8 \cdot y_1 + 16 \cdot y_0
     =  2 \cdot 32 + 4 \cdot 8 + 8 \cdot 2 + 16 \cdot 1
     =  128 \\
\end{eqnarray*}

The above calculation suggests the following claim.

\medskip
{\bf Claim.}
The solution to the recurrence is $y_0 = 1$ and $y_n = 2^{2n-1}$ for $n
\geq 1$.
\medskip
}

\problempart Prove your guess correct using strong induction.

\solution {

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
$y_0 = 1$ and $y_n = 2^{2n-1}$ for $n \geq 1$.  In the base case,
$P(0)$ holds trivially.  In the inductive step, assume $P(0), \ldots,
P(n)$ to prove $P(n+1)$.  By the definition of $y_{n+1}$, we have:

\begin{eqnarray*}
y_{n+1} & = &   \sum_{i=1}^{n+1} y_{n+1-i} \cdot 2^i \\
    & = &   y_0 \cdot 2^{n+1} + \sum_{i=1}^n y_{n+1-i} \cdot 2^i \\
    & = &   1 \cdot 2^{n+1} + \sum_{i=1}^n 2^{2(n+1-i)-1} \cdot 2^i \\
    & = &   2^{n+1} + 2^{2n+1} \cdot \sum_{i=1}^{n} \frac{1}{2^i} \\
    & = &   2^{n+1} + 2^{2n+1} \cdot \left( 1 - \frac{1}{2^n} \right) \\
    & = &   2^{2(n+1) - 1}
\end{eqnarray*}

In the second step, we split out the special term of the summation
that contains $y_0$.  The third step uses the induction hypotheses,
and in the fourth step we pull a constant out of the summation.  The
fifth equation follows from the formula for the sum of a geometric
series.  The last step is simplication.

This shows that $P(0), \ldots, P(n)$ imply $P(n+1)$, and the claim is
proved by strong induction.
\end{proof}
}

\end{problemparts}   
\end{problem}
