\documentclass[12pt]{article}
\usepackage[]{graphicx}
\usepackage[]{amsmath}
\usepackage[]{amsthm}
\usepackage[]{amssymb}
\usepackage[hmargin=.6in,vmargin=.6in]{geometry}
\pagestyle{empty}
\newtheorem{thm}{Theorem}
\newtheorem*{thma}{Theorem}
\theoremstyle{remark}
\newtheorem{rem}{Remark}
\begin{document}
\begin{center}
\textbf{Math 475 Big Problems, Batch 2}
\end{center}
\noindent \textbf{Big Problem 6: Closed Form Formula for the Fibonacci Sequence}.
\begin{enumerate}
\item We call a sequence $A_n$ \emph{Fibonacci-esque} if it has the property $A_{n+2} = A_{n+1} + A_n$.
\item Find all geometric sequences that are Fibonacci-esque. That is, all numbers $C$ such that the sequence $A_n = kC_n$ is Fibonacci-esque (for constant $k$).
\item Prove linear combinations of Fibonacci-esque sequences have to be Fibonacci-esque.
\item Find a closed-form formula for the famous Fibonacci sequence ${1, 1, 2, 3, 5, 8, \dots}$ by finding a sum of Fibonacci-esque geometric sequences that has the famous values.
\end{enumerate}
\noindent \textbf{Big Problem 7: Irrational Numbers}.
\begin{enumerate}
\item Use an argument similar to Euclid's method to prove $\sqrt[n]{2}$ is irrational for any natural number $n > 1$.
\item Use an argument similar to Euclid's method to prove that $\sqrt{p}$ is irrational for $p$ prime.
\end{enumerate}
\noindent \textbf{Big Problem 8: Power Set Sizes}.
\begin{enumerate}
\item A set $S$ has $N$ distinct elements. How many distinct subsets are there? (Be sure to include $S$ and $\{ \}$.) Explain why your formula works.
\item The power set of $S$, written $P(S)$, is the set of subsets of $S$. Prove that the cardinality of $P(S)$ is strictly larger than the cardinality of $S$ when $S$ is finite.
\item Consider the general case of a possibly infinite set $S$. To deal with comparing cardinalities of infinite sets, we say that sets $A$ and $B$ ``have the same cardinality'' if and only if $A$ fits into $B$ and $B$ fits into $A$. Here we define ``$A$ fits into $B$'' to mean there is an injection from $A$ to $B$.
\item Consider the power set of the rational numbers, $P(\mathbb{Q})$. Show that the real numbers fit into $P(\mathbb{Q})$. Use this fact, and our previously established uncountability of the reals, to give a proof that $P(\mathbb{Q})$ does not fit into $\mathbb{Q}$.
\noindent \emph{Note}: There is a theorem called the Bernstein-Schroeder Theorem which says that $A$ and $B$ have the same cardinality if and only if there is a bijection between them. You are allowed to use that theorem for this problem set.
\item Prove that the cardinality of $P(S)$ is always larger than the cardinality of $S$, even when $S$ is infinite! (\emph{Hint}: Suppose there is a bijection $f:S \to P(S)$. Now consider $\{s \in S \; | \; s \notin f(s) \}$.)
\end{enumerate}
\end{document}