\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 3
}

Please submit in class at 8:00am on Thursday 13th July
\end{center}

\subsection*{Exercises}

\begin{enumerate}[1.]
\item Consider the sequence $(a_n)_{n \ge 0}$ defined by
$$a_0=2, \quad a_1=3 \quad \text{and} \quad a_{n+2} = 3a_{n+1} - 2a_n \text{ for all } n \in \mathbb{N}$$
\begin{enumerate}[(a)]
\item Evaluate the terms $a_2$, $a_3$, $a_4$ and $a_5$. \points{1}
\item Find an expression for a general term $a_n$ of the sequence in terms of $n$ only.
\points{2}
\item Prove by induction that your expression is valid.
\points{7}
\end{enumerate}

\item
\begin{enumerate}[(a)]
\item Which natural numbers less than fifteen can be expressed as $3u+7v$ for some $u,v \in \mathbb{N}$? Prove your claims. \points{1}
\item Which natural numbers less than fifteen \textit{cannot} be expressed as $3u+7v$ for some $u,v \in \mathbb{N}$? Prove your claims. \points{2}
\item Prove that every natural number greater than or equal to fifteen can be expressed as $3u+7v$ for some $u,v \in \mathbb{N}$. [\textit{Hint: use strong induction.}]
\points{7}
\end{enumerate}

\item Fix $c,d \in \mathbb{R}$ and suppose that a sequence $(x_n)_{n \ge 0}$ satisfies
$$x_0 = 0, \quad x_1=1 \quad \text{and} \quad x_{n+2}=cx_{n+1}+dx_n \text{ for all } n \in \mathbb{N}$$
Suppose furthermore that $c^2+4d > 0$, and let $\alpha$ and $\beta$ be the (distinct, real) roots of the quadratic $x^2-cx-d$. [This means that $x^2-cx-d=(x-\alpha)(x-\beta)$ for all $x \in \mathbb{R}$.]
\begin{enumerate}[(a)]
\item Find real numbers $A$ and $B$, defined in terms of $\alpha$ and $\beta$, such that $x_0 = A+B$ and $x_1 = A\alpha + B\beta$. \points{2}
\item Using the values of $A$ and $B$ you found in part (a), prove by induction that $x_n = A\alpha^n + B\beta^n$ for all $n \in \mathbb{N}$. \points{6}
\item The \textit{Fibonacci sequence} is the sequence $(f_n)_{n \ge 0}$ defined by
$$f_0=0, \quad f_1=1 \quad \text{and} \quad f_{n+2}=f_{n+1}+f_n \text{ for all } n \in \mathbb{N}$$
Using your answers to parts (a) and (b) to prove that
$$f_n=\dfrac{\varphi^n-\psi^n}{\sqrt{5}} \text{ for all } n \in \mathbb{N}$$
where $\varphi = \dfrac{1+\sqrt{5}}{2}$ and $\psi = \dfrac{1-\sqrt{5}}{2}$.
\points{2}
\end{enumerate}
\end{enumerate}

\vfill

\begin{center}
\textit{More tasks on the next page}
\end{center}

\subsection*{Other tasks}
\begin{enumerate}[1.]
\setcounter{enumi}{3}
\item Typeset your answer to (at least) one of the previous questions using \LaTeX{}. Upload the \texttt{.tex} file to the Homework 2 page on Canvas. Print out the resulting \texttt{.pdf} document and submit it along with your answers to the other questions.
\points{5}
\end{enumerate}

\subsection*{Optional but recommended tasks {\normalfont (not for credit)}}

\begin{enumerate}[1.]
\setcounter{enumi}{4}
\item Typeset all of your homework solutions using \LaTeX{}.
\item The number $\varphi$ in Q3(c) is known as the \textit{golden ratio}. Despite its simple definition as being the greatest of the two roots of the quadratic $x^2-x-1$, approximations to it appear all over the place in nature. This has fascinated people over the ages, who have had reactions ranging from, `Oh, that's interesting!', to outright mysticism. Read about some of the occurrences of $\varphi$ in the real world.
\item Suppose that the first two terms of the sequence in Question 3 had been defined by $x_0=a$ and $x_1=b$, where $a$ and $b$ are two more fixed real numbers. Repeat Q3(a) in this case, and show that Q3(b) remains true. Apply your result to the case where $a=2$, $b=3$, $c=3$ and $d=-2$ and verify that your answer agrees with that of Q1(b).
\item Suppose in Question 3 that we had $c^2+4d=0$, so that $\alpha = \beta$. What goes wrong? Show that, in this case, we have $x_n = (A+Bn)\alpha^n$ for all $n \in \mathbb{N}$, where $A$ and $B$ are real numbers, defined in terms of $\alpha$, that you should find.
\end{enumerate}

\end{document}