\documentclass[12pt]{article}

\begin{document}

\centerline{\bf Untimed Midterm. Morally Due April 11}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\NCU}{{\rm NCU}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\C}{{\sf C}}
\newcommand{\Rpos}{{\sf R}^+}

\centerline{\bf WARNING: THIS MIDTERM IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}


\begin{enumerate}


\item
(16 points)

\begin{enumerate}
\item
(0 points) 
In this problem $\C$ is the complex numbers. 

Write a program that does the following:
Given $A,B$ consider the recurrence:

$a_0=1$

$a_1=2$

$(\forall n\ge 2)[a_n = Aa_{n-1} + Ba_{n-2}].$

FIND $C,D,\alpha_1,\alpha_2\in \C$  (use an approximation to 5 places)
such that 

$$a_n = C\alpha_1^n + D\alpha_2^n.$$


\item 
(0 points but you will need this)
Write a program that will, given $M$, 
run the program in part a for all 
$1\le A\le M$ and $-M\le B \le M$
and generates a table of the following form:


$M=2$: 
\[
\begin{array}{|c|c|c|c|c|}
\hline 
A & B & \alpha_1 & \alpha_2 & \max\{\alpha_1,\alpha_2\} \cr 
\hline 
1 & -2 & 1.2 +i & 2.3 -i & 2.3-i \cr 
1 & -1 & 2.2 & 4.3 & 4.3 \cr 
1 & 0  & 8.2 & 1.3 & 8.2 \cr 
1 & 1  & 9.2 & 11.3 & 11.3 \cr 
1 & 2  & 19.2 & 111.3 & 111.3 \cr 
2 & -2 & 1.2 & 2.3 & 2.3 \cr 
2 & -1 & 2.2 & 4.3 & 4.3 \cr 
2 & 0  & 8.2 & 1.3 & 8.2 \cr 
2 & 1  & 9.2 & 11.3 & 11.3 \cr 
2 & 2  & 19.2 & 111.3 & 111.3 \cr 
\hline
\end{array}
\]

(for complex number $a+bi$ the size is $a^2+b^2$. We use this for defining the max.) 

\vfill

\centerline{\bf GOTO NEXT PAGE FOR MORE ON THIS PROBLEM}

\newpage


\item
(0 points) 
Email Emily your code.

\item
(5 points)
IF you ran the code on $M$, how many rows will the program generate?
Show your work in deducing the number. 

\item
(11 points)
Run the code on $M=3$ and submit the table.

\item
(Extra Credit) Say something intelligent about how $A$ affects
MAX ALPHA and how $B$ affects MAX ALPHA. Which has a bigger effect? 
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage 

\item
(16 points)
Emily might {\it teach} 250H in Spring 2023 (Bill is going on sabbatical). 
She will need help designing problems! In this problem you will help her!

She wants to ask a question of the following form (With $A,B,C$ replaced by positive
natural numbers).

HERE IS THE PROBLEM SHE WANTS TO ASK:

{\it 
Let $a_n$ be defined as follows.


$a_1=5$

$(\forall n\ge 2)[ a_n = Ba_{n-1}^2 + Ca_{\floor{n^{1/3}}}]$

Show by strong induction that

$(\forall n\ge 1)[a_n \equiv 5 \pmod {12} ]$

Include Base Case, IH, and IS.

} 

Now for YOUR PROBLEM: Use constructive induction to find
9 pairs $(B,C)$ such that 

$$(\forall n\ge 1)[a_n \equiv 5 \pmod {12} ].$$

You will need to have a Base Case, IH, and IS. 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(18 points- 6 points each)
In this problem all of the $x_i$ are natural numbers.
And remember that 0 is a natural number. 
\begin{enumerate}
\item
How many elements are in the following set:

$$\{ (x_1,\ldots,x_n) \colon (x_i\ge 0) \wedge (x_1+\cdots+x_{10}=100) \}.$$

\item
How many elements are in the following set:

$$\{ (x_1,\ldots,x_n) \colon (x_i\ge 1) \wedge (x_1+\cdots+x_{10}=100) \}.$$


\item
How many elements are in the following set:

$$\{ (x_1,\ldots,x_n) \colon (x_i\ge 2) \wedge (x_1+\cdots+x_{10}=100) \}.$$

\item
(Extra Credit)
How many elements are in the following set:

$$\{ (x_1,\ldots,x_n) \colon (x_i\ge i) \wedge (x_1+\cdots+x_{10}=100) \}.$$


\end{enumerate}
\end{enumerate}
\end{document}