\documentclass[12pt]{amsart}

\usepackage{amsmath, amssymb, amsthm}
\usepackage[margin=0.5in]{geometry}
\usepackage[pdflang={en-US}]{hyperref}
\usepackage[shortlabels]{enumitem}

\usepackage{tikz}

\renewcommand{\thesection}{\Alph{section}}

\newcommand{\scs}[1]{\begin{scshape}#1\end{scshape}}
\newcommand{\inv}{^{-1}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\nmod}[1][n]{\left(\text{mod}\ #1\right)}

\newtheorem*{theorem}{Theorem}
\newtheorem*{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem{problem}{}
\newtheorem*{challenge}{Challenge}
\newtheorem*{example}{Example}

\newcommand{\thm}[1]{\begin{theorem}#1\end{theorem}}
\newcommand{\prop}[1]{\begin{proposition}#1\end{proposition}}
\newcommand{\prob}[1]{\begin{problem}#1\end{problem}}
\newcommand{\dfn}[1]{\begin{definition}#1\end{definition}}
\newcommand{\chal}[1]{\begin{challenge}#1\end{challenge}}
\newcommand{\eg}[1]{\begin{example}#1\end{example}}

\newcommand{\abs}[1]{\left| #1 \right|}

\title{Induction I}
\date{Marh 23, 2022}

\begin{document}\ 

\vspace{-.25in}

\maketitle

\vspace{-.2in}

\prob{
Prove that for any $n \in \NN$ and any sets $A_1, A_2, \dots, A_n$, \[
\overline{A_1  \cup A_2 \cup \dots \cup A_n} = \overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n}.
\]
}

\vfill

\prob{
Find the flaw in the following proof.

\prop{
For any $n \in \NN$ and any lines $\l_1, l_2, \dots, l_n$ in $\RR^2$, the intersection $\l_1 \cap l_2 \cap \dots \cap l_n$ is either $\emptyset$ or $l_i$ for some $i \in \{1, 2, \dots, n\}$.  
}

\begin{proof}[Proof by induction]
Base case: $n=1$. 
This means we have just one line $l_1$. 
Clearly $l_1 = \l_1$, which establishes the base case.

Now suppose that $k \in \NN$ and that for any lines $\l_1, l_2, \dots, l_k$ in $\RR^2$, $\l_1 \cap l_2 \cap \dots \cap l_k$ is either $\emptyset$ or $l_i$ for some $i \in \{1, 2, \dots, k\}$.
Let $\l_1, l_2, \dots, l_{k+1}$ be lines in $\RR^2$.
If $\l_1 \cap l_2 \cap \dots \cap l_{k+1} = \emptyset$, then we're done.
If $\l_1 \cap l_2 \cap \dots \cap l_{k+1} \neq \emptyset$, then $\l_1 \cap l_2 \cap \dots \cap l_k \neq \emptyset$.
Then by the inductive hypothesis, $\l_1 \cap l_2 \cap \dots \cap l_k = \l_i$ for some $i \in \{1, 2, \dots, k\}$.
Fix this $i$ so we can continue to work with this particular line $l_i$.
Then we have $\emptyset \neq \l_1 \cap l_2 \cap \dots \cap l_k \cap l_{k+1} = l_i \cap l_{k+1} = l_i \cap l_i \cap \dots \cap l_i \cap l_{k+1}$ where $l_i$ is repeated $k-1$ times.
This means we can again apply the inductive hypotheses to conclude that $l_i \cap l_{k+1}$ is either $l_i$ or $l_{k+1}$.
This suffices to establish the inductive step.
Therefore the proposition holds for every $n \in \NN$.




\end{proof}
}

% \prob{
% Fill in the missing steps of the following proof.

% \thm{$1 + 2 + 4 + \dots + 2^n = 2^{n+1} -1$ for every $n \in \NN$.}
% \begin{proof}[Proof (by induction on $n$)]
% Base case: $n = 1$.
% \fbox{\parbox[c][.5in]{4.1in}{Then }}

% Inductive step.
% Suppose $k \in \NN$ and $1 + 2 + 4 + \dots + 2^k = 2^{k+1} -1$.
% Then \[
% 1 + 2 + 4 + \dots + 2^{k+1} = \left( 1 + 2 + 4 + \dots + 2^k \right) + 2^{k+1} \]
% \hspace{.455\textwidth}\fbox{\parbox[t][1.5in]{.53\textwidth}{= }}

% Therefore, by induction, $1 + 2 + 4 + \dots + 2^n = 2^{n+1} -1$ for every $n \in \NN$.
% \end{proof}
% }

% \prob{
% Use induction (on $n$) to prove that for all $n \in \NN$, $3^n \geq 1+2^n$.
% }

% \newpage

% \prob{
% Use induction (on $n$) to prove de Moivre's formula: for all $n \in \NN$ and all $x \in \RR$ \[  \boxed{ \left( \cos x + i \sin x \right)^n = \cos (nx) + i \sin(nx) } \]
% (where $i = \sqrt{-1}$).
% You might need to use the following trig identities: \begin{align*}
% \cos(a+b) = \cos a \cos b - \sin a \sin b \\
% \sin(a+b) = \sin a \cos b + \cos a \sin b
% \end{align*}
% }

% \vfill

% \chal{
% Prove that for all $n \in \NN$, $8 \mid \left(5^{2n} - 1\right)$.
% }

\end{document}