\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,colortbl,graphicx}


\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}

\newcommand{\R}{\mathbb{R}}

\begin{document}

\title{General Mathematics and CPS II}
\author{Exercise 20}
\date{May 4, 2012}
\maketitle


\def\e{\mathrm{e}}
\def\i{\mathrm{i}}
\def\d{\mathrm{d}}

\begin{enumerate}

\item Solve the difference equation
\begin{gather*}
  t_n = 2 \, t_{n-1} + 2^{n+1} \,, \\
  t_1 = 0 \,.
\end{gather*}
\item Let $u \colon [0, 2\pi] \to \mathbb R$ be defined via the
Fourier series
\[
  u(x) = \sum_{k \in \mathbb Z} \hat u_k \, \e^{\i k x} \,.
\]
Show that its derivative $w(x) = u'(x)$, assuming it exists, has 
Fourier coefficients
\begin{equation*}
  \hat w_k = \i k \, \hat u_k \,.
  \tag{*}
\end{equation*}

\item The previous question suggests a way to differentiate a function
$u \colon [0, 2\pi] \to \mathbb R$ numerically: First, sample $u$ on
the equidistant grid $x_j = jh$ with $h = 2 \pi/N$.  Second, compute
the Fourier coefficients of its trigonometric interpolant $v$ as
described in Section~3 of the handout.  Third, use (*) on the Fourier
coefficients $\hat v_k$.  Finally, take the inverse DFT to obtain the
derivative sampled on the grid.

A practical difficulty lies in the convention that standard FFT
software libraries take the indexing convention $j=0,\dots,N-1$ and
$k=0,\dots,N-1$.  In particular, the input and output data arrays are
arranged in precisely this order.  Trigonometric interpolation, on the
other hand, requires that $k=-N/2,\dots,N/2-1$.  With which factor,
then, must the $i$th element, with respect to the order imposed by the
software, of the vector $\hat {\boldsymbol v}$ be multiplied so that
differentiation is computed correctly?


\end{enumerate}
\end{document}
