\documentclass[11pt,twoside,macpsfig,amssymb]{article}

\usepackage{amsmath}
\usepackage{latexsym}
%\usepackage{graphics}
\input{macros-course}
\newcommand{\solution}[1]{}
\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\newcommand{\kth}{\ensuremath{\mbox{th}}}
\newcommand{\kmod}[1]{\ensuremath{(\mathrm{mod\ }#1)}}
\newcommand{\ignore}[1]{}
\newcommand{\spac}{\vspace{4mm}}
\newcommand{\hspac}{\vspace{2mm}}


\def\la{\lambda}
\def\ni{\noindent}


\begin{document}


\begin{problems}

\problem

The "sum mod  3" of an $n$-bit string $v_1\ldots v_n$ where $v_i\in \{0,1\}$
is the sum of the bits of the string mod 3.
Let $a_n$ denote the number of
$n$-bit strings for which the sum of the bits is 0 mod 3,
$b_n$ the number of
$n$-bit strings for which the sum of the bits is 1 mod 3,
and $c_n$ denote the number of
$n$-bit strings for which the sum of the bits is 2 mod 3.
\bparts
\ppart Write a system of recurrences for $a_n$, $b_n$, and $c_n$
and explain how you arrived at this system.
\solution{ Let us call a string
a type-0 string if the sum of its bits is 0 mod 3,
a type-1 if the sum of its bits is 1 mod 3, and
a type-2 if the sum of its bits is 2 mod 3.

An $n$ bit string $v=v'\cdot v_n$ 
(where $v'$ is length $n-1$ and $v_n\in \{0,1\}$, )
will be type $i$ if and only if (1) either $v_n=0$ and $v'$ is type $i$ or
(2) $v_n=1$ and $v'$ is type $j$ such that $j+1=i$ mod 3.

Thus, the system if recurrences will be:

$$(1)\hbox{	}a_n=a_{n-1}+c_{n-1}$$
$$(2)\hbox{	}b_n=a_{n-1}+b_{n-1}$$
$$(3)\hbox{	}c_n=2^n - (a_n+b_n)$$
}
\ppart
Specify boundry conditions.
\solution{
$a_0=b_0=c_0=0$, $a_1=b_1=1$, $c_1=0$.}
\ppart Generate a linear recurrence for $b_n$.
\solution{
First, substitute the definition of $c_n$ from equation (3) into equation (1),
to get $a_n=a_{n-1}+2^{n-1}-a_{n-1}-b_{n-1} = 2^{n-1}-b_{n-1}$. 
Now, substitute $a_n$ in equation (2)  to get the linear recurrence 
$b_{n}=2^{n-2}-b_{n-2}+ b_{n-1}$.}
\ppart Is your recurrence homogeneous or not?
\solution{ not}
\ppart
What is the associated characteristic equation of the linear recurrence generated?
\solution
{$x^2-x+1=0$ SHAFI - unfortunately no solution over the reals... this boggles my mind}

\eparts


\end{problems}
\end{document}
