%%PRPROB2-PROBS.TEX, 6042 F01

\begin{problems}
\problem Rosen, 3.2.8 %sum of cubes

\solnospace{to appear}
%see instructor manual

\problem Rosen 3.3.6 %Fibonnaci recurrence

\solnospace{to appear}
%see instructor manual

\problem Explain how to convert an proof by induction with base case 4
into an ordinary proof by induction, i.e., with base case 0.

\solnospace{Replace the hypothesis $P(n)$ by $Q(n)$ where $Q(n) \eqdef P(n+4)$.}

\problem Vellemen Exercise 6.2.5

\solnospace{\textbf{Induction step}: We must show that if $\card{A}=n+1$,
then $A$ has $(n+1)n/2$ 2-subsets.

Let $B \eqdef A-\set{a}$ for any $a \in A$.  So $\card{B} = n$ and by
induction hypothesis $B$ has $n(n-1)/2$ 2-subsets.  The 2-subsets of $A$
are simply those of $B$, plus the $n$ 2-subsets of $A$ which contain $a$.
So $A$ has $n(n-1)/2 + n = (n(n-1) + 2n)/2 = (n+1)n/2$ 2-subsets.}
\end{problems}

