homework7w
Author:
Geoffrey Bostany
Last Updated:
10 years ago
License:
Creative Commons CC BY 4.0
Abstract:
homework7m
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{amssymb}
\pagestyle{fancy}
\lhead{Homework 7w}
\chead{Geoffrey Bostany}
\rhead{Recitation number 202}
\begin{document}
\begin{enumerate}
\item Proof by induction on $n$ \\
INDUCTION HYPOTHESIS: Assume the claim is true when $n=k$ for some integer $k \geq 1$. In other words, we assume that \\ $1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{2^k} \geq 1 + \frac{k}{2}$ \\
BASE CASE: $n=1$ \\ $1+\frac{1}{2^(1)} = \frac{3}{2} \geq 1 + \frac{(1)}{2} = \frac{3}{2}$ \\ thus the case holds true for the base case \\
INDUCTION STATEMENT: we want to prove the claim when $n=k+1$ \\
$1+\frac{k}{2} + \frac{1}{2^k+1} + \frac{1}{2^k+2} +... + \frac{1}{2^{(k+1)}} \geq 1 + \frac{k+1}{2}$ \\ $\frac{1}{2^k+1} + \frac{1}{2^k+2} +... + \frac{1}{2^{(k+1)}} \geq 1 + \frac{k+1}{2} - 1 - \frac{k}{2}$ \\ $\frac{1}{2^k+1} + \frac{1}{2^k+2} +... + \frac{1}{2^{(k+1)}} \geq \frac{1}{2}$ \\
now given this statement, we know two things. First, we know that $\frac{1}{2^{(k+1)}}$ is the smallest element on the left hand side because it has the largest denominator. Second, we know that there are $2^n$ terms on the left hand side. We can prove this by calculating the difference between $2^{n+1}$ and $2^n$ below \\
$2^{n+1} - 2^n = x$ \\ $2^{n}(2-1) = x \\ 2^n = x$\\ So since there are $2^n$ terms and the smallest term is $\frac{1}{2^{(k+1)}}$, we can assume that the left hand side is atleast $2^n * \frac{1}{2^{(k+1)}}$ \\ $2^n x \frac{1}{2^{(k+1)}} = \frac{2^n}{2^{(k+1)}} = \frac{1}{2}$ \\ So the sum is atleast $\frac{1}{2}$ which proves the our induction statement and thus proves the claim.
\item proof by induction on $n$ \\
INDUCTION HYPOTHESIS: Assume that the claim is true when $n=k$ for some positive integer $k$. In other words, we assume that \\ $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{k}} < 2\sqrt{n}$ \\
BASE CASE: n=1 \\
$\frac{1}{\sqrt{1}} < 2\sqrt{1} \\
1 < 2$ thus the claim holds true for the base case \\
INDUCTION STATEMENT: $n=k+1$ \\
$2\sqrt{n} + \frac{1}{\sqrt{n+1}} < 2\sqrt{n+1}$ \\
\item Proof by induction on n \\
INDUCTION HYPOTHESIS: assume that the claim is true $n=k$, in other words, assume that if we divide a sheet of paper into polygonal regions using lines that completely cross the paper and no two lines are directly on top of each other, it is true that we can always color the various regions using only two colors, so that any two regions that share a boundary line have different colors. \\
BASE CASE: $n=1$ \\ We draw a single line across a sheet of paper, clearly dividing it into 2 distinct regions. Thus we can color these two regions two different colors. This proves the claim for the base case \\
INDUCTION STATEMENT: we want to prove the claim when $n=k+1$ \\assume that we have a sheet of paper with $k+1$ lines and you remove any line. It now has $n$ lines which we have already proved can be colored according to our constraints. Now we add back that one line. In order to adjust to the constraints, we can hold all regions on one particular side of our $k+1$ line constant, and then recolor all regions on the other side of our $k+1$ line the opposite color of what it currently is. by doing this, we can satisfy the constraints thus proving the claim by the principle of induction.
\item We want to prove that $\forall n \in\mathbb{Z}$, there exists 2 positive integers $a>b$ such that $10 \mid (n^a-n^b)$ \\ In other words we want to prove that \\ $(n^a-n^b) = 10k$ for some integer $k$\\
Now, to have the differenc between two numbers divisible by 10, both of their "ones" digits must be the exact same integer. If we assume that $b=1$, this means that we can prove this claim if we can prove that any number $n$ multiplied by itself enough times will always arrive at a number that has its "ones" digit the same as $n$'s. \\ This must be true because by the pigeon hole principle, if we multiply $n$ by itself 9 times, there will be atleast 2 numbers with the same digit in the "ones" place. This can be demonstrated as the following digits multiplied by themselves (I only record the "ones" digits) \\
$1 x 1 = 1 \\ 2 x 2 = 4 x 2 = 8 x 2 = 6 x 2 = 2 \\ 3 x 3 = 9 x 3 = 7 x 3 = 1 x 3 = 3 \\ 4 x 4 = 6 x 4 = 4 \\ 5 x 5 = 5 \\ 6 x 6 = 6 \\ 7 x 7 = 9 x 7 = 3 x 7 = 1 x 7 = 7 \\ 8 x 8 = 4 x 8 = 2 x 8 = 6 x 8 = 8 \\ 9 x 9 = 1 x 9 = 9$
\\
Thus the claim is true
\item Consider 4 consecutive points in a row, by the pigeon hole principle, there will always be at least 2 points that are the same color. Thus we have two points of the rectangle. Now consider the rows of 4 directly underneath our row. There are $3^4$ different combinations of rows possible. \\
Now consider a any row of 4 and the 81 rows directly underneath it so that we have a 4x82 block, by the pigeon hole principle, there is atleast one row that appears twice. Thus we can form a rectangle with it's points and prove the claim.
\end{enumerate}
\end{document}