\documentclass[12pt]{article}

\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{mathrsfs}
\usepackage{enumerate}
\usepackage[arrow,curve]{xy}


% Blackboard Bold
\newcommand{\R}{\mathbb{R}}

% Caligraphic
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cU}{\mathcal{U}}


% Set notation 
\newcommand{\emp}{\varnothing}

% Greek
\newcommand{\eps}{\varepsilon}

% Arrows
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\into}{\hookrightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\xr}{\xrightarrow}
\newcommand{\xl}{\xleftarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\rr}{\rightrightarrows}

\newcommand{\HLINE}{\hbox to\hsize{\hrulefill}}

\newcommand{\Prob}[1]{%\filbreak
\par\vspace{1\jot}\noindent\HLINE\vspace{1\jot}
\noindent\textbf{Problem #1.}\space\noindent\ignorespaces}

\allowdisplaybreaks

\newcommand{\Soln}{{\it Solution.} }

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{fact}[thm]{Fact}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem*{guid}{Guideline}

\begin{document}

\begin{center}
{\large Extra Credit Homework Problems}
\end{center}

Note: these problems are of varying difficulty, so you might want to assign different point values for the different problems. I have suggested the point values each problem should be worth.

These problems are meant to introduce new concepts, give applications, challenge students, reinforce the concepts learned in class, and also prepare them for upcoming material.

\section{Mathematical Induction}
\begin{enumerate}[(1)]
\item (+2 points) Use mathematical induction to prove
\[\sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}{6}\]
\item (+2 points) Use mathematical induction to prove
\[\sum_{j=1}^n j^3 = \left(\frac{n(n+1)}{2}\right)^2\]
\item (+5 points) Given one piece of chocolate which consists of $n$ chocolate squares joined together at the edges, how many times does one have to break the chocolate (along the edges) until one is left with only $1 \times 1$ squares? Use strong mathematical induction to prove your answer! 
\end{enumerate}


\section{Integrals}
  
\begin{enumerate}[(1)]

\item (+4 points) Recall that, given an interval $[a, b]$ and a function $f(x)$ defined on $[a, b]$, $\cR(f, \cU_N)$ is the upper Riemann sum and $\cR(f, \cL_N)$ is the lower Riemann sum, for the function $f(x)$ using a uniform partition of the interval $[a, b]$ of order $N$. Suppose $f(x)$ is continuous and increasing on $[a, b]$. Show that
\[\cR(f, \cU_N) - \cR(f, \cL_N) = (f(b) - f(a)) \cdot \frac{b-a}{N}.\]
Show that a similar statement is true if $f(x)$ is continuous and decreasing. Conclude that $f$ is integrable on $[a, b]$ in either case, i.e.
\[\lim_{N \to \infty} (\cR(f, \cU_N) - \cR(f, \cL_N)) = 0.\]
For a continuous function $f$ on $[a, b]$, we can break up $[a, b]$ into intervals where the function is increasing and where the function is decreasing and thus prove (using the reasoning here) that any continuous function $f$ is integrable on $[a, b]$.

\item (+2 points) The {\it Fresnel sine integral}, defined by 
\[S(x) = \int_0^x \sin(\frac{\pi}{2} t^2)\,dt\]
is an important function in the theory of optical diffraction. Determine the intervals on which this function is concave up.

\item (+5 points) Let $\ln^{[0]}(x) = x, \ln^{[1]}(x) = \ln(x), \ln^{[2]}(x) = \ln(\ln(x)), \dots.$ In general, let
\[\ln^{[n]}(x) = \ln(\ln(\cdots (\ln(x))\cdots ))\]
be the composition of $n$ functions $\ln(x)$. Recall the product notation:
\[\prod_{j=0}^n f(j) = f(0)f(1)f(2)\cdots f(n).\]
Using mathematical induction and $u$-substitution, prove that
\[\int \frac{dx}{\prod_{j=0}^n \ln^{[j]}(x)} = \ln^{[n+1]}(x) + C\]
Do not simply differentiate $\ln^{[n+1]}(x)$. Rather, use $u$-substitution to find the integral.

\item (+6 points) Show that if a function $f(x)$ is continuous everywhere and $f(x + y) = f(x) + f(y)$ for all real numbers $x$ and $y$, then $f(x) = ax$, where $a = f(1)$. {\it Hint: show by induction that for every positive integer $n$, $f(n) = na$. Then show this is true for all integers. Then prove $f(x) = ax$ for all rational numbers $x$. Then (you can take this for granted) it follows that $f(x) = ax$ for all real numbers by continuity: if $\{b_n\}$ is a sequence of rational numbers that converges to an irrational number $x$ then} 
\[f(x) = f(\lim_{n \to \infty} b_n) = \lim_{n \to \infty} f(b_n) = \lim_{n \to \infty} ab_n = ax.\]

\item (+6 points) Show that if a function $f(x)$ is continuous everywhere and $f(x + y) = f(x)f(y)$ for all real numbers $x$ and $y$, then either $f(x) = 0$ for all $x$ or $f(x) = a^x$ where $a = f(1)$ is a {\it positive} number.

\item (+6 points) Show that if a function $f(x)$ is continuous on $(0, \infty)$ and $f(xy) = f(x) + f(y)$ for all real numbers $x$ and $y$, then either $f(x) = 0$ for all $x$ or $f(x) = \log_a x$, where $a$ is a fixed {\it positive} number.

\item (+6 points) Show that if a function $f(x)$ is continuous on $(0, \infty)$ and $f(xy) = f(x)f(y)$ for all real numbers $x$ and $y$, then either $f(x) = 0$ for all $x$ or $f(x) = x^a$, where $a$ is a  fixed real number.

\item (+5 points) Find two functions $f(x), g(x)$ (neither of which is $0$) and two of their antiderivatives $F(x), G(x)$, respectively, such that $F(x)G(x)$ is an antiderivative of $f(x)g(x)$. The point is, it's really hard to actually find such functions, so certainly the product of antiderivatives is not in general an antiderivative of the product.

\item (+4 points total)
\begin{enumerate}[(a)]
\item Prove the reduction formula
\[\int \cos^n x\,dx = \frac1n \cos^{n-1}x \sin x + \frac{n-1}n \int \cos^{n-2}x\,dx\] 
\item Use part (a) to evaluate $\int \cos^2 x\,dx$.
\item Use parts (a) and (b) to evaluate $\int \cos^4 x\,dx$.\\
\end{enumerate}

\item (+2 points each) Use integration by parts to prove the reduction formulas:
\[\int (\ln x)^n\,dx = x (\ln x)^n - n \int (\ln x)^{n-1}\,dx\]
\[\int \tan^n x\,dx = \frac{\tan^{n-1}x}{n-1} - \int \tan^{n-2} x\,dx (n \ne 1)\]
\\

\item (+2 points total) Show that 
\[\sin x \sin y = \frac12(\cos(x-y) - \cos(x+y))\]
and use this formula to compute
\[\int \sin(3x)\sin(9x)\,dx.\]

\item (+2 points) Find
\[\int \csc^3 x \,dx\]
without using any reduction formulas.

\item (+2 points) Find
\[\int \frac{4x + 5}{x^2 + 2x + 5}\,dx.\]
{\it Hint: This integral requires completing the square and splitting the numerator correctly.}

\item (+3 points) Find
\[\int \frac{x^3 + 2x^2 + 23x - 44}{(x^2 - 2x + 1)(x^2 + 4x + 13)}\,dx\]

\item (+5 points) Find
\[\int \sqrt{\tan x}\,dx.\]
{\it Hint:}
\begin{align*}
u^4 + 1 &= u^4 + 2u^2 + 1 - 2u^2\\
&= (u^2 + 1)^2 - (\sqrt 2 u)^2\\
&= (u^2 + 1 - \sqrt 2 u)(u^2 + 1 + \sqrt 2 u)
\end{align*}


\item (+4 points) Consider the solid formed by revolving the curve $y = 1/x$ for $x \ge 1$ around the $x$-axis. Find the volume of the solid. Now prove that the surface area of the solid is infinite! ({\it Hint:} you need not compute the entire integral to show it is infinite).

\end{enumerate}



\section{Differential Equations}

\begin{enumerate}[(1)]

\item (+2 points) The following (linear differential) equation relates the velocity $v$ of a particle to the position $s$ of the particle at time $t$:
\[v + \csc(t)s = \csc t + \cot t, s(\pi/2) = 0\]
Find an explicit expression for $s(t)$.

\item (+2 points) The following (separable differential) equation relates the velocity $v$ of a particle to the position $s$ of the particle at time $t$:
\[2s(s - 4)\cos^2 t = v\]
If the particle starts at position $s = \frac{4}{1 - e^4}$ meters ($m$), find the position of the particle at any given time $t$.

\item (+4 points) The following (linear differential) equation relates the acceleration $a$ of a particle to its velocity $v$ at time $t$:
\[a - v = e^t - 5\]
If the particle starts at position $s = 0\; m$ with velocity $v = 5\; m/s$ (meters per second), find its position $s(t)$ at any given time $t$.

\end{enumerate}

\section{Sequences and Series}

\begin{enumerate}[(1)]

\item (+3 points) Find the $n$-th derivative of $f(x) = (2x - 3)^{-1}$, and use mathematical induction to prove your answer is correct.

\item (+3 points) Find the $n$-th derivative of $f(x) = xe^x$, and use mathematical induction to prove your answer is correct.


\item (+2 points) Use mathematical induction to prove that
\[\sum_{j=0}^n a^j = 1 + a + a^2 + a^3 + \cdots + a^n = \frac{1 - a^{n+1}}{1 - a}\]


The Fibonacci sequence $\{F_n\}$ is defined by
\[F_n = \left\{\begin{array}{ll}
1, & \text{if } n = 1\\
1, & \text{if } n = 2\\
F_{n-1} + F_{n-2}, & \text{if } n > 2
\end{array}\right.\]

The first few terms of the Fibonacci sequence are:
\[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots\]

\item (+2 points) Leonardo of Pisa (known as Fibonacci) considered the following problem in his book Liber Abaci (1202): Suppose that rabbits live forever and that every month each pair produces a new pair which becomes productive at age 2 months. If we start with one newborn pair, how many pairs of rabbits will we have in the $n$-th month? Show that the answer is $F_n$ (actually, he considered the problem with $n = 12$).

\item (+2 points) Prove that $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$ for all $n \ge 1$.

\item (+2 points) Show by induction that $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ for all $n \ge 2$.

\item (+2 points) Show by induction that $F_{n+2}F_{n-1} - F_{n+1}F_n = (-1)^n$ for all $n \ge 2$.

\item (+3 points) Show that the following infinite continued fraction gives the golden ratio $\phi = \frac{1 + \sqrt 5}{2}$:
\[1 + \frac{1}{1 + \frac{1}{1 + \cdots}}\]
Define a sequence $\{a_n\}$ by $a_1 = 1, a_{n+1} = 1 + \frac{1}{a_n}$. If you think about it, the infinite continued fraction above is the limit $L = \lim_{n \to \infty} a_n$, if the limit exists. {\it You may assume that the limit does indeed exist.} Now use the fact that $\lim_{n \to \infty} a_{n+1} = \lim_{n \to \infty} a_n = L$ to find $L$.

\item (+3 points) Assume that the limit $\lim_{n \to \infty} F_{n+1}/F_n$ exists. Show that this limit equals the golden ratio $\phi = \frac{\sqrt 5 + 1}{2}$. {\it Hint: Define $a_n = F_{n+1}/F_n$, show that $a_{n+1} = 1 + 1/a_n$, and use the same reasoning as in the last exercise (you must complete the last exercise to get credit for using it).}


\item (+4 points) Find the sum:
\[\sum_{n=2}^\infty \frac{4n}{(n^2-1)^2}\]
{\it Hint: use partial fractions.}

\item (+3 points each) Find the values of $p$ for which the series converges:

\begin{align*}
& (a) \sum_{n=3}^\infty \frac{1}{n(\ln n)^p}\\
& (b) \sum_{n=1}^\infty n(1 + n^2)^p\\
& (c) \sum_{n=2}^\infty \frac{\ln n}{n^p}
\end{align*}

\item (+2 points) Give an example of two series $\sum_{n=1}^\infty a_n$ and $\sum_{n=1}^\infty b_n$ such that $\lim_{n \to \infty} (a_n/b_n) = 0$, $\sum_{n=1}^\infty b_n$ diverges, and $\sum_{n=1}^\infty a_n$ converges.

\item (+2 points) Show that if $a_n > 0$ for all $n$ and $\lim_{n \to \infty} na_n = L \ne 0$ then $\sum_{n = 1}^\infty a_n$ diverges.

\item (+5 points each) Test the following series for convergence:
\begin{align*}
& (a) \sum_{n=1}^\infty \frac{1}{n + n \cos^2 n}\\
& (b) \sum_{n=1}^\infty \frac1{n^{1 + 1/n}}\\
& (c) \sum_{n=2}^\infty \frac{1}{(\ln n)^{\ln n}}\\
& (d) \sum_{n=1}^\infty (\sqrt[n]{2} - 1)
\end{align*}

\item (+4 points) Find the decimal approximation of $\sin(0.01)$ correct to 12 decimal places WITHOUT the use of a calculator, as follows. First use the Maclaurin series for $\sin x$ and plug in $0.01$. Then use the Alternating Series Test (the part concerning the error) to find the smallest number of terms you need in the resulting series so that the error is less than $10^{-12}$. Now add up those terms and compute the decimal approximation.

\item (+4 points) Using the approach in the last problem, find the decimal approximation of $\cos(0.01)$ correct to 9 decimal places WITHOUT the use of a calculator. Show all your work.

\item (+5 points) We know that the sum of the series $\sum_{n=0}^\infty r^n$ is $\frac{1}{1 - r}$ when $|r| < 1$. In this exercise we will find the sum of the series 
\[\sum_{n=1}^\infty nr^n = r + 2r^2 + 3r^3 + 4r^4 + \cdots\]
under the same condition, $|r| < 1$. Begin with the power series
\[\sum_{n=0}^\infty x^n = 1 + x + x^2 + \cdots = \frac{1}{1 - x}\]
Now differentiate both sides and then multiply both sides by $x$ to find a formula for
\[\sum_{n=1}^\infty nx^n.\]
Find the sums
\begin{align*}
& (a) \sum_{n=1}^\infty \frac{n}{2^n}\\
& (b) \sum_{n=2}^\infty \frac{n}{3^n}\\
& (c) \sum_{n=3}^\infty \frac{n}{4^n}
\end{align*}

\item (+5 points) The same thing can be done for a finite sum as well: start with the formula
\[\sum_{k=0}^n r^k = \frac{1 - r^{k+1}}{1 - r}\]
that we found in class and differentiate both sides, then multiply both sides by $x$ to find the formula for
\[\sum_{k=1}^n kr^k.\]
This formula works for any $r$, not just those with $|r| < 1$. Now find the sums
\begin{align*}
& (a) \sum_{k=1}^{100} k2^k\\
& (b) \sum_{k=2}^{200} \frac{k}{3^k}\\
& (c) \sum_{k=3}^{1000} \frac{k}{4^k}
\end{align*}
You should see that the last two sums are very close in value to the last two sums in the first problem.

\item (+2 points) Use the definition of the Taylor series for $f(x)$ centered at $x = 2$,
\[f(x) = \sum_{n=0}^\infty f^{(n)}(2)\frac{(x-2)^n}{n!},\]
and the formula for the $n$-th derivative of $f(x) = xe^x$ we found in class (namely $f^{(n)}(x) = (x + n)e^x$) to find the Taylor series for $xe^x$ centered at $x = 2$.

\item (+5 points) Use the definition of the Maclaurin series for $f(x)$,
\[f(x) = \sum_{n=0}^\infty f^{(n)}(0)\frac{x^n}{n!},\]
to find the Maclaurin series for $f(x) = (2x - 3)^{-1}$ (see problem 1 on the extra credit due October 27).


\item (+5 points) Find the Maclaurin series for $\tan^{-1}(x)$ as follows. Start with the Maclaurin series for $\frac{1}{1 + x^2}$, the derivative of $\tan^{-1}(x)$, by writing it as
\[\frac{1}{1 - (-x^2)}\]
and recognizing the latter as the sum of a certain geometric series. Then integrate both sides to get
a power series equal to $\tan^{-1}(x) + C$. Finally, plug in a well-chosen value for $x$ to find the constant $C$. This is the really cool part: use the power series you found to get a series representation of $\pi/4$, which is $\tan^{-1}(1)$. Thus, multiplying by $4$, we get a series that adds up to $\pi$!
\end{enumerate}

\section{Modular Arithmetic}

The notation $a \equiv b \pmod m$, for integers $a, b$, and $m$, means $a - b$ is divisible by $m$, i.e. there is an integer $k$ (positive or negative or 0) such that $a - b = km$.

\begin{enumerate}[(1)]

\item (+2 points) Show that if $a, b, c$, and $d$ are integers such that $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then $a + c \equiv b + d \pmod m$ and $ac \equiv bd \pmod m$.

\item (+2 points) Show that if $a$ and $b$ are integers such that $a \equiv b \pmod m$ and $n$ is any positive integer, then $a^n \equiv b^n \pmod m$.

\item (+5 points) Show by induction that if $n$ and $m$ are positive integers and $n \equiv -1 \pmod m$ then one can explicitly compute
\[\int x^ne^{x^m}\,dx\]
{\it Hint: the positive numbers $n$ such that $n \equiv -1 \pmod m$ are
\[m-1, 2m-1, 3m-1, \dots.\]
You do not have to actually compute the integral! But +5 more points if you do and if you can prove that what you got is the right answer (by using induction).}

\item (+3 points) Prove that the remainder when a number is divided by $3$ is the same as the remainder when the sum of the digits of the number is divided by $3$. Thus, a number is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

\item (+1 point total) Find the remainder when the following numbers are divided by $3$: 
\begin{enumerate}[(a)]
\item 123456789
\item 135791113151719
\item 2468101214161820
\item 999897969594939291
\end{enumerate}

\end{enumerate}

\section{Combinatorics}

\begin{enumerate}
\item (+1 point) How many permutations are there of the words RANDOMIZE, ARBITRARY, and MASSACHUSETTS?

\item (+2 points) Use the formula
\[{n \choose r} = \frac{n!}{r!(n-r)!}\]
to prove algebraically that
\[{n \choose r} + {n \choose r + 1} = {n+1 \choose r+1}\]

\item (+8 points) Prove
\[(x + y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k}\]
as follows. First show
\begin{equation}
(x+y)^n = \sum_{k=0}^n C_kx^ky^{n-k}
\label{eqn:CmbBinom}
\end{equation}
 where $C_k$ are some constant coefficients, i.e. in the product $(x+y)^n$, all the terms are of the form $x^ky^{n-k}$ for some $k$. Now, show that 
\[C_k = {n \choose k}\]
as follows. In equation (\ref{eqn:CmbBinom}), fix $y$ to be a constant and take the derivative with respect to $x$ $k$ times; then fix $x$ and take the derivative with respect to $y$ ($n-k$) times. Show that the only term that remains is the one where the power of $x$ is $k$ and the power of $y$ is $n-k$, and $C_k$ is as above.

\end{enumerate}



\end{document}


