\documentclass{article} 
\usepackage{graphicx} 
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}

\begin{document} 

\title{COT 3100C Homework \#6} 
\author{Jason Yau} 

\maketitle 
\pagebreak 

\section{Question 1} 
Let $F_i$ denote the $ith$ Fibonacci number. Prove by induction on $n$ that, for all positive integers $n$:
$$\sum_{i=1}^{n} F_{2i} = F_{2n+1}-1$$
\underline{Base Case}: Let n = 1: 
$$\text{LHS} = \sum_{i=1}^{1} F_{2i} = F_2 = 1$$
$$\text{RHS} = F_{2+1}-1 = F_3 -1 = 2 - 1 = 1$$
Thus, the base case holds for the given assertion for n = 1.
\\
\\\underline{Inductive Hypothesis}: Assume for an arbitrarily chosen positive integer 
\\n = k that:
$$\sum_{i=1}^{k} F_{2i} = F_{2k+1}-1$$
\\\underline{Inductive Step}: Prove for $n=k+1$ that: 
$$\sum_{i=1}^{k+1} F_{2i} = F_{2(k+1)+1}-1$$

\begin{equation*} 
\begin{split}
 \sum_{i=1}^{k+1} F_{2i} &= \sum_{i=1}^{k} F_{2i} + \sum_{i=k+1}^{k+1} F_{2i} \\
 &= F_{2k+1}-1+ \sum_{i=k+1}^{k+1} F_{2i} \text{, Using the Inductive Hypothesis.} \\
 &= F_{2k+1}-1+F_{2(k+1)} = F_{2k+1}+F_{2k+2}-1\\
 &= F_{2k+3}-1 = F_{2(k+1)+1}-1 \text{, as desired.}
\end{split}
\end{equation*}

This completes the proof of the Inductive Step. Therefore, we can conclude that for all positive integers n that:
$$\sum_{i=1}^{n} F_{2i} = F_{2n+1}-1$$
\pagebreak
\section{Question 2}
Define a sequence, $a_i$, as follows: 
\\\indent$a_0$ = 0, $a_1$ = 1, $a_2$ = 3, $a_n$ = $3a_{n-1} + 2a_{n-2}$, for all ints $n > 2$.
\\
\\Using induction on $n$, prove for all positive integers, $n$, that:

\begin{equation*} 
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{n}
 = 
 \begin{bmatrix}
  a_{n+1} & 2a_n \\
  a_n & 2a_{n-1} \\
 \end{bmatrix} 
\end{equation*}

\underline{Base Case}: Let n = 1: 
\begin{equation*} 
\begin{split}
 \text{LHS} =
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{1}
 =
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}
\end{split}
\end{equation*}

\begin{equation*} 
\begin{split}
 \text{RHS} =
 \begin{bmatrix}
  a_{1+1} & 2a_1 \\
  a_1 & 2a_{1-1} \\
 \end{bmatrix}
 =
 \begin{bmatrix}
  a_2 & 2a_1 \\
  a_1 & 2a_0 \\
 \end{bmatrix}
 =
 \begin{bmatrix}
  3 & 2\cdot 1 \\
  1 & 2\cdot 0 \\
 \end{bmatrix}
 =
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}
\end{split}
\end{equation*}
Thus, the base case holds for the given assertion for n = 1.
\\\\\underline{Inductive Hypothesis}: Assume for an arbitrarily chosen positive integer 
\\n = k that:
\begin{equation*} 
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{k}
 = 
 \begin{bmatrix}
  a_{k+1} & 2a_k \\
  a_k & 2a_{k-1} \\
 \end{bmatrix} 
\end{equation*}
\\\underline{Inductive Step}: Prove for $n=k+1$ that: 
\begin{equation*} 
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{k+1}
 = 
 \begin{bmatrix}
  a_{(k+1)+1} & 2a_{k+1} \\
  a_{k+1} & 2a_{(k+1)-1} \\
 \end{bmatrix} 
  = 
 \begin{bmatrix}
  a_{k+2} & 2a_{k+1} \\
  a_{k+1} & 2a_{k} \\
 \end{bmatrix} 
\end{equation*}

\begin{equation*} 
\begin{split}
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{k+1}
 &=
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{k}
 \cdot
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{1}
 \\
 &=
 \begin{bmatrix}
  a_{k+1} & 2a_k \\
  a_k & 2a_{k-1} \\
 \end{bmatrix} 
 \cdot
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}
 \text{, Using the Inductive Hypothesis.}
 \\
 &=
 \begin{bmatrix}
  a_{k+1}\cdot 3+2a_k\cdot 1 & a_{k+1}\cdot 2+2a_k\cdot 0 \\
  a_k\cdot 3+2a_{k-1}\cdot 1 & a_k\cdot 2+2a_{k-1}\cdot 0 \\
 \end{bmatrix}
 \\
 &=
 \begin{bmatrix}
  3a_{k+1}+2a_k & 2a_{k+1} \\
  3a_k+2a_{k-1} & 2a_k \\
 \end{bmatrix}
 \\
 &=
 \begin{bmatrix}
  a_{k+2} & 2a_{k+1} \\
  a_{k+1} & 2a_k \\
 \end{bmatrix}
 \text{, using the sequence definition, as desired.}
\end{split}
\end{equation*}

This completes the proof of the Inductive Step. Therefore, we can conclude that for all positive integers n that:

\begin{equation*} 
 \begin{bmatrix}
  3 & 2 \\
  1 & 0 \\
 \end{bmatrix}^{n}
 = 
 \begin{bmatrix}
  a_{n+1} & 2a_n \\
  a_n & 2a_{n-1} \\
 \end{bmatrix} 
\end{equation*}
\pagebreak
\section{Question 3}
Let $a > 1$ be a positive integer. Using induction on n, prove for all positive integers n that:
$$(a^2-a+1)\mid ((a-1)^{n+1}+a^{2n-1})$$
\underline{Base Case}: Let n = 1: 

\begin{equation*}
\begin{split}
 (a-1)^{1+1}+a^{2(1)-1} &= (a-1)^{2}+a \\
 &= (a^2-2a+1+a) \\
 &= (a^2-a+1) \\
 &= (a^2-a+1)\mid (a^2-a+1)
\end{split}
\end{equation*}
\\Thus, the base case holds for the given assertion for n = 1.
\\\\\underline{Inductive Hypothesis}: Assume for an arbitrarily chosen positive integer 
\\n = k that:
$$(a^2-a+1)\mid ((a-1)^{k+1}+a^{2k-1})$$
$$\exists x\in\mathbb{Z} \mid((a-1)^{k+1}+a^{2k-1})=x(a^2-a+1),$$ by the definition of divisibility.
\\\\\underline{Inductive Step}: Prove for $n=k+1$, that: 
$$(a^2-a+1)\mid ((a-1)^{(k+1)+1}+a^{2(k+1)-1})$$
$$\equiv(a^2-a+1)\mid ((a-1)^{k+2}+a^{2k+1})$$

\begin{equation*}
\begin{split}
 (a-1)^{k+2}+a^{2k+1} &= (a-1)^{k+1}(a-1)+a^{2k-1}(a^2) \\
 &= (a-1)^{k+1}(a-1)+a^{2k-1}(a-1)+a^{2k-1}(a^2-a+1) \\
 &= (a-1)((a-1)^{k+1}+a^{2k-1})+a^{2k-1}(a^2-a+1) \\
 &= (a-1)(x)(a^2-a+1)+a^{2k-1}(a^2-a+1)\text{, Using the Inductive Hypothesis.} \\
 &= (a^2-a+1)(x(a-1)+a^{2k-1})
\end{split}
\end{equation*}
x, a $\in\mathbb{Z} \implies (x(a-1)+a^{2k-1})\in\mathbb{Z}$.
\\
\\Since $(a^2-a+1)\mid(a^2-a+1)(x(a-1)+a^{2k-1})$, the proof of the Inductive Step is complete. Therefore, we can conclude for all positive integers n that:
$$(a^2-a+1)\mid ((a-1)^{n+1}+a^{2n-1})$$.
\pagebreak
\section{Question 4}
Using mathematical induction on n, prove for all positive integers n, that:
$$\sum_{i=1}^{n^2} \sqrt{i} \geq \frac{n(4n^2-3n+5)}{6}$$
\underline{Base Case}: Let n = 1: 
$$\text{LHS} = \sum_{i=1}^{1} \sqrt{i} = \sqrt{1} = 1$$
$$\text{RHS} = \frac{1(4(1)^2-3(1)+5)}{6} = \frac{4-3+5}{6} = 1$$
$1 \geq 1$, so the base case holds for the given assertion for n = 1.
\\\\\underline{Inductive Hypothesis}: Assume for an arbitrarily chosen positive integer 
\\n = k that:
$$\sum_{i=1}^{k^2} \sqrt{i} \geq \frac{k(4k^2-3k+5)}{6}$$
\\\\\underline{Inductive Step}: Prove for $n=k+1$, that: 
$$\sum_{i=1}^{(k+1)^2} \sqrt{i} \geq \frac{(k+1)(4(k+1)^2-3(k+1)+5)}{6}$$
$$= \frac{(k+1)(4(k^2+2k+1)-3k-3+5)}{6}$$
$$= \frac{(k+1)(4k^2+5k+6)}{6} = \frac{4k^3+9k^2+11k+6}{6}$$

\begin{equation*}
\begin{split}
 \sum_{i=1}^{(k+1)^2} \sqrt{i} &= \sum_{i=1}^{k^2} \sqrt{i}+\sum_{i=k^2+1}^{(k+1)^2} \sqrt{i} \\
 &= \sum_{i=1}^{k^2} \sqrt{i}+\sum_{i=k^2+1}^{k^2+2k+1} \sqrt{i} \\
 &= \sum_{i=1}^{k^2} \sqrt{i}+\sum_{i=k^2+1}^{k^2+2k} \sqrt{i}+\sum_{i=k^2+2k+1}^{k^2+2k+1} \sqrt{i} \\
\end{split}
\end{equation*}

continued on page 6...
\pagebreak
$$\geq \sum_{i=1}^{k^2} \sqrt{i}+\sum_{i=k^2+1}^{k^2+2k} \sqrt{k^2}+\sum_{i=(k+1)^2}^{(k+1)^2} \sqrt{i} $$
$$= \sum_{i=1}^{k^2} \sqrt{i}+\sum_{i=k^2+1}^{k^2+2k} (k)+k+1 $$
$$= \sum_{i=1}^{k^2} \sqrt{i}+((k^2+2k)-k^2)(k)+k+1 $$
$$ \sum_{i=1}^{k^2} \sqrt{i}+2k^2+k+1 $$
$$\geq \frac{k(4k^2-3k+5)}{6}+2k^2+k+1\text{, Using the Inductive Hypothesis.}$$
$$= \frac{k(4k^2-3k+5)}{6}+\frac{6(2k^2+k+1)}{6}$$
$$= \frac{k(4k^2+9k+11)+6}{6}$$
$$= \frac{4k^3+9k^2+11k+6}{6}$$
$$\geq \frac{4k^3+9k^2+11k+6}{6}\text{, as desired.}$$
This completes the proof of the Inductive Step. Therefore, we can conclude that for all positive integers n that:
$$\sum_{i=1}^{n^2} \sqrt{i} \geq \frac{n(4n^2-3n+5)}{6}$$
\pagebreak
\section{Question 5}
Give a summary of the academic contributions of Grigori Perelman.
\\
\\
Grigori Perelman is a renowned Russian mathematican. He was born in Leningrad in 1966, and from a young age, he showed excellence in mathematics. In 1982, at the age of 15-16, he was a member of the Soviet Union's International Mathematical Olympiad and won their team a gold medal with a perfect score. He went and studied mathematics at the Leningrad State University and finished his PhD in 1990. He was invinited to do research for multiple universities in the U.S., including Berkeley and Stanford. He did some research mainly in geometry; in convex geometry, negatively curved hypersurfaces, Alexandrov spaces, and comparsion geometry.
\\
\\After his studies, he went on to do research and solved many mathematical problems. He is most renowned for solving the Poincare Conjecture and Thurston's geometrization conjecture in 2002-2003, which involves shapes with 4+ dimensions and was unsolved for decades. In 2006, he was offered the Fields Medal, one of the most prestigious awards in mathematics. However, he declined the award as he didn't need the attention. In his own words, "I'm not interested in money or fame; I don't want to be on display like an animal in a zoo." He later also refused to accept a million dollar prize in 2010 for his contributions. As of now, he is currently dormant from most mathematical work.
\\
\\Sources:
\\1. \url{https://en.wikipedia.org/wiki/Grigori_Perelman}
\\2. \url{https://www.npr.org/templates/story/story.php?storyId=125658261}
\end{document}