% LaTeX solution template for Math 235 % ----------------------------------------------------------------- % Like most advanced LaTeX files, this one begins with a lot of % boilerplate. You don't need to understand (or even read) most of it. % All you need to do is fill in your name, email address, % and the number of the pset. (Search for "METADATA" to find the place % for this.) Then, you can go straight to the "EXERCISE 1" % section and start writing your solutions. % The "VARIOUS USEFUL COMMANDS" section is probably worth taking a % look at at some point. % If you are here to learn about LaTeX, search for % "START READING HERE" and start reading there. %---------------------------------------------------------------------------------------- % PACKAGES AND OTHER DOCUMENT CONFIGURATIONS %---------------------------------------------------------------------------------------- \documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size \usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs \usepackage[english]{babel} % English language/hyphenation \usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages \usepackage{mathrsfs} % More math packages \usepackage{sectsty} % Allows customizing section commands \allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites \usepackage{hyperref} % Turns cross-references into hyperlinks, % and defines \url and \href commands. \usepackage{graphicx} % For embedding graphics files. \usepackage{framed} % For the "leftbar" environment used below. \usepackage{ifthen} % Used for the \powset command below. \usepackage{lastpage} % for counting the number of pages \usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage} \usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} % This is a powerful tool to draw vector % graphics inside LaTeX. In particular, you can % use it to draw graphs. \usepackage{verbatim} % For the "verbatim" environment, in which % special symbols can be used freely without % confusing the compiler. (And it's typeset in % a constant-width font.) % Useful, e.g., for quoting code (or ASCII art). %\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4) \setlength\parindent{20pt} % Makes indentation for paragraphs longer. % This makes paragraphs stand out more. %---------------------------------------------------------------------------------------- % VARIOUS USEFUL COMMANDS %---------------------------------------------------------------------------------------- % The commands below might be convenient. For example, you probably % prefer to write $\powset[2]{V}$ for the set of $2$-element subsets % of $V$, rather than writing $\mathcal{P}_2(V)$. % Notice that you can easily define your own commands like this. % Caveat: Some of these commands need to be properly "guarded" when % they occur in subscripts or superscripts. So you should not write % $K_\CC$, but rather $K_{\CC}$. \newcommand{\CC}{\mathbb{C}} % complex numbers \newcommand{\RR}{\mathbb{R}} % real numbers \newcommand{\QQ}{\mathbb{Q}} % rational numbers \newcommand{\NN}{\mathbb{N}} % nonnegative integers \newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k % (syntax: "\Z{k}") \newcommand{\ZZ}{\mathbb{Z}} % integers \newcommand{\id}{\operatorname{id}} % identity map \newcommand{\lcm}{\operatorname{lcm}} % Lowest common multiple. For historical reasons, LaTeX has a \gcd % command built in, but not an \lcm command. The preceding line % rectifies that. \newcommand{\rev}{\operatorname{rev}} % reversal of a walk \newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}} % $\powset[k]{S}$ stands for the set of all $k$-element subsets of % $S$. The argument $k$ is optional, and if not provided, the result % is the whole powerset of $S$. \newcommand{\set}[1]{\left\{ #1 \right\}} % $\set{...}$ compiles to {...} (set-brackets). \newcommand{\abs}[1]{\left| #1 \right|} % $\abs{...}$ compiles to |...| (absolute value, or size of a set). \newcommand{\tup}[1]{\left( #1 \right)} % $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets). \newcommand{\ive}[1]{\left[ #1 \right]} % $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value). \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} % $\floor{...}$ compiles to |_..._| (floor function). \newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)} % $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph). \newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)} % $\edges{...}$ compiles to E(...) (edge set of a graph). \newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)} % $\arcs{...}$ compiles to A(...) (arc set of a digraph). \newcommand{\lf}[2]{#1^{\underline{#2}}} % $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$. % This is a notation for the falling factorial. \newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}} % $\underbrack{...1}{...2}$ yields % $\underbrace{...1}_{\substack{...2}}$. This is useful for doing % local rewriting transformations on mathematical expressions with % justifications. For example, try this out: % $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $ \newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height \newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line. \newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}} % $\explain{...}$ interprets the "..." as text (you can % nest some math inside by putting it in $...$'s as you % would in any other text block) and puts it in parentheses. %---------------------------------------------------------------------------------------- % MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW % THE SIGN %---------------------------------------------------------------------------------------- % The following are hacks to ensure that sums (such as % $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the % $n$) underneath and above the sign, as opposed to on its right. % Same for products (\prod), set unions (\bigcup) and set % intersections (\bigcap). Remove the 8 lines below if you do not want % this behavior. \let\sumnonlimits\sum \let\prodnonlimits\prod \let\cupnonlimits\bigcup \let\capnonlimits\bigcap \renewcommand{\sum}{\sumnonlimits\limits} \renewcommand{\prod}{\prodnonlimits\limits} \renewcommand{\bigcup}{\cupnonlimits\limits} \renewcommand{\bigcap}{\capnonlimits\limits} %---------------------------------------------------------------------------------------- % ENVIRONMENTS %---------------------------------------------------------------------------------------- % The incantations below define how theorem environments % (\begin{theorem} ... \end{theorem}) and their likes will look like. \newtheoremstyle{plainsl}% {8pt plus 2pt minus 4pt}% {8pt plus 2pt minus 4pt}% {\slshape}% {0pt}% {\bfseries}% {.}% {5pt plus 1pt minus 1pt}% {}% % Environments which make the text inside them slanted: \theoremstyle{plainsl} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} % Environments that don't: \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{examples}[theorem]{Examples} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newenvironment{statement}{\begin{quote}}{\end{quote}} \newenvironment{fineprint}{\begin{small}}{\end{small}} %---------------------------------------------------------------------------------------- % METADATA %---------------------------------------------------------------------------------------- \newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE \newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE \newcommand{\psetnumber}{8} % ENTER THE NUMBER OF THIS PSET HERE %---------------------------------------------------------------------------------------- % HEADER AND FOOTER %---------------------------------------------------------------------------------------- \ihead{Solutions to homework set \#\psetnumber} % Page header left \ohead{page \thepage\ of \pageref{LastPage}} % Page header right \ifoot{\myname} % left footer \ofoot{\mymail} % right footer %---------------------------------------------------------------------------------------- % TITLE SECTION %---------------------------------------------------------------------------------------- \title{ \normalfont \normalsize \textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s) \horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule \huge Math 235: Mathematical Problem Solving, \\ Fall 2026: Homework \psetnumber\\% The assignment title \horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule } \author{\myname} \begin{document} \maketitle % This command causes the title part to be printed. %---------------------------------------------------------------------------------------- % EXERCISE 1 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 1} \subsection{Problem} Recall the Fibonacci sequence $\tup{f_0, f_1, f_2, \ldots}$, defined by $f_0 = 0$ and $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for all $n \geq 2$. Let $n \in \NN$. Let $P \in \QQ\ive{X}$ be a polynomial of degree $\leq n$ that satisfies $P\tup{k} = f_k$ for each $k \in \set{0,1,\ldots,n}$. Find $P\tup{n+1}$. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 2 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 2} \subsection{Problem} Let $P \in \RR\ive{X}$ be a polynomial such that $P \tup{\cos \alpha} = P \tup{\sin \alpha}$ for all $\alpha \in \RR$. Prove that $P = Q \tup{X^4 - X^2}$ for some $Q \in \RR\ive{X}$. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 3 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 3} \subsection{Problem} A polynomial $P \in \ZZ\ive{X}$ is said to be \emph{primitive} if the gcd of its coefficients is $1$. Let $Q$ and $R$ be two primitive polynomials in $\ZZ\ive{X}$. Prove that their product $QR$ is also primitive. \subsection{Hint} A bunch of integers are coprime if and only if they have no common prime divisor. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 4 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 4} \subsection{Problem} Let $n \in \NN$. Prove that we have $X^2 + X + 1 \mid X^{2n} + X^n + 1$ in $\ZZ\ive{X}$ if and only if $3 \nmid n$ in $\ZZ$. \subsection{Hint} First, define $N := X^2 + X + 1$, and show that $X^3 \equiv 1 \mod N$ in $\ZZ\ive{X}$. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 5 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 5} \subsection{Problem} Let $n \in \NN$. Let $P \in \QQ\ive{X}$ be a polynomial of degree $\leq n$ that satisfies $P\tup{k} = \dfrac{1}{k}$ for each $k \in \set{1,2,\ldots,n+1}$. Show that $P\tup{0} = \dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{n+1}$. \subsection{Hint} Take the derivative on both sides of the equality \[ XP - 1 = \tup{X-1} \tup{X-2} \cdots \tup{X-\tup{n+1}} \cdot Q \] in the solution to Exercise 8.5.1 on Worksheet 8. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 6 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 6} \subsection{Problem} Let $n$ be an even positive integer. Let $u_1, u_2, \ldots, u_n$ be the $n$ roots of the polynomial $X^n - nX + 1$. Prove that \[ \dfrac{1}{u_1+1} + \dfrac{1}{u_2+1} + \cdots + \dfrac{1}{u_n+1} = \dfrac{2n}{n+2}. \] \subsection{Hint} Find a degree-$n$ polynomial with roots $\dfrac{1}{u_1+1}, \ \dfrac{1}{u_2+1},\ \ldots,\ \dfrac{1}{u_n+1}$. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 7 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 7} \subsection{Problem} Let $P\in\ZZ\ive{X}$ be a polynomial of even degree whose all coefficients (not counting the zero coefficients in front of powers that are larger than the degree) are odd. Prove that $P$ has no rational root. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 8 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 8} \subsection{Problem} Let $P = c_0 X^0 + c_1 X^1 + \cdots + c_n X^n$ be a polynomial in $\ZZ\ive{X}$ (with $c_0, c_1, \ldots, c_n \in \ZZ$). Let $r \in \QQ$ be a root of $P$. Prove that $c_n r^i + c_{n-1}r^{i-1} + \cdots + c_{n-i}r^0 \in \ZZ$ for each $i \in \set{0,1,\ldots,n}$. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 9 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 9} \subsection{Problem} Let $a_0, a_1, \ldots, a_n$ be $n+1$ pairwise distinct integers (where $n \in \NN$). Prove that for any $s \in \NN$, the number \[ \sum_{j=0}^{n} \dfrac{a_j^s}{\prod_{k \neq j}\tup{a_j-a_k}} \] (where the ``$\prod_{k \neq j}$'' sign means a product over all $k \in \set{0,1,\ldots,n}$ satisfying $k \neq j$) is an integer. \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 10 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 10} \subsection{Problem} Let $n \in \NN$. Prove that \[ \sum_{i=0}^{n} \tup{-1}^{n-i} \dbinom{n}{i} i^{n+1} = \dfrac{n \tup{n+1}!}{2}. \] \subsection{Hint} Alas, the polynomial $P := X^{n+1}$ has degree $n+1$, which is too high for an obvious application of Lagrange interpolation. Can you find a polynomial $Q$ that has degree $\leq n$ but a sum $\sum_{i=0}^{n} \tup{-1}^{n-i} \dbinom{n}{i} Q\tup{i}$ closely related to the sum on the left hand side? \subsection{Solution} ... %---------------------------------------------------------------------------------------- % EXERCISE 11 %---------------------------------------------------------------------------------------- \horrule{0.3pt} \\[0.4cm] \section{Exercise 11} \subsection{Problem} Let $P \in \RR\ive{X}$ be a polynomial such that $P\tup{x} \geq 0$ for all $x \in \RR$. Prove that $P$ can be written in the form $P = Q_1^2 + Q_2^2 + \cdots + Q_k^2$ for some polynomials $Q_1, Q_2, \ldots, Q_k \in \RR\ive{X}$. \subsection{Hint} First, show that if two polynomials $P_1$ and $P_2$ can be written in this form, then so can their product $P_1 P_2$. Next, show that every polynomial of the type $\tup{X-z} \tup{X-\overline{z}}$ for two conjugate complex numbers $z=a+bi$ and $\overline{z}=a-bi$ can be rewritten in this form. Finally, use the Fundamental Theorem of Algebra on $P$. \subsection{Solution} ... \horrule{0.3pt} \\[0.4cm] \begin{thebibliography}{99999999} % \bibitem[Grinbe20]{20f}Darij Grinberg, \textit{Math 235: Mathematical Problem Solving}, 10 August 2021. \newline \url{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf} \end{thebibliography} \end{document}