\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}