\documentclass[11pt]{article}

\usepackage{times,mathptm}
\usepackage{pifont}
\usepackage{exscale}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{epsfig}

\textwidth 6.5in
\textheight 9in
\oddsidemargin -0.0in
\topmargin -0.0in

\parindent 0pt     % How much the first word of a paragraph is indented. 
\parskip 0pt       % How much extra space to leave between paragraphs.

\begin{document}

\begin{center}             % If you only centering 1 line use \centerline{}
\begin{LARGE}
{\bf CSci 243 Homework 7}
\end{LARGE}
\vskip 0.25cm      % vertical skip (0.25 cm)

**My name**
\end{center}

\begin{enumerate}

\item (2 points each) Give a recursive definition for each of the following sequences
$\{a_n\}$ for $n=1, 2, 3, \ldots$.

\begin{enumerate}
\item $a_n=4n-2$
\item $a_n=n(n+1)$
\item $a_n=(\frac{1}{2})^n$
\end{enumerate} 

\item For string $w=a_1a_2\cdots a_n$, the reversal of the string is defined as
$w^R=a_n\cdots a_2a_1$.
\begin{enumerate}
\item (1 point) What is $\epsilon^R$? What is $(10110)^R$?
\item (4 points) Give a recursive definition of the reversal of a string.
\item (6 points) Use structural induction to prove that $(w_1w_2)^R=w_2^Rw_1^R$. (Use your recursive defintion).
\end{enumerate}

\item (7 points) 
A palindrome is a string that reads the same forward and backward, i.e., $w=w^R$.
Give a recursive algorithm in pseudocode that checks whether a given string $w$ is a palindrome.

\item  (7 points)
Give a recursive algorithm in pseudocode that finds the maximum number among $n$ integers.

\item (9 points) Use the iterative approach to solve the following recurrence relations.
\begin{enumerate}
\item $a_n=a_{n-1}+3$ and $a_0=0$
\item $a_n=a_{n-1}+n$ and $a_0=0$
\item $a_n=(n+1)a_{n-1}$ and $a_0=2$
\end{enumerate}



\end{enumerate}



\end{document}
