Homework 8w

\documentclass[11pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{amssymb}
\pagestyle{fancy}

\lhead{Homework 8m}
\chead{Geoffrey Bostany}
\rhead{Recitation number 202}

\begin{document}
\begin{enumerate}
\item We will prove by induction on $n$ \\ INDUCTION HYPOTHESIS: assume that the claim is true when $n=k$, In other words, we assume that  $\sum\limits_{i=1}^{n}\lfloor\frac{i}{2}\rfloor = \lfloor\frac{k^2}{4}\rfloor$ \\ 

BASE CASE: k=1 \\ $\lfloor\frac{1}{2}\rfloor = \lfloor\frac{1^2}{4}\rfloor$ \\ $0 = 0$ thus the claim is true for the base case. \\ 

INDUCTION STATEMENT: n=k+1 \\ $\lfloor\frac{k^2}{4}\rfloor + \lfloor\frac{k+1}{2}\rfloor = \lfloor\frac{(k+1)^2}{4}\rfloor$ \\ 

Now we can have two cases: k is either odd or k is even \\ 

Case 1: k is even, thus k can be written as $2q$ \\ $\lfloor\frac{k^2}{4}\rfloor$ = $\lfloor\frac{4q^2}{4}\rfloor$ = $q^2$ \\ $\lfloor\frac{k+1}{2}\rfloor$ = $\lfloor\frac{2q+1}{2}\rfloor = \lfloor q + \frac{1}{2}\rfloor = q$ \\ $\lfloor\frac{(k+1)^2}{4}\rfloor$ = $\lfloor\frac{(2q+1)^2}{4}\rfloor$ = $\lfloor\frac{(4q^2+4q+1}{4}\rfloor$ = $q^2 + q$ \\

Thus by equating the two sides again we have \\ $q^2 + q = q^2 + q$ and the claim is true when k is even. \\

Case 2: k is odd, thus k can be written as $2q+1$ \\ $\lfloor\frac{k^2}{4}\rfloor$ = $\lfloor\frac{(2q+1)^2}{4}\rfloor$ = $\lfloor\frac{4q^2+4q+1}{4}\rfloor$ = $q^2+q$ \\ $\lfloor\frac{k+1}{2}\rfloor$ = $\lfloor\frac{2q+2}{2}\rfloor$ = $q+1$ \\ $\lfloor\frac{(k+1)^2}{4}\rfloor$ = $\lfloor\frac{(2q+2)^2}{4}\rfloor$ = $\lfloor\frac{(4q^2+8q+4}{4}\rfloor$ = $q^2+2q+1$ \\ 

Thus by equating the two sides again we have \\ $q^2+q+q+1$ = $q^2+2q+1$ and the claim is true when k is odd. \\ 

Thus the claim is always true. 

\item Proof by induction on n \\ BC: n=1 \\ we can produce 1 by using the second fibonnaci number of 1.
IH: assume the claim is true for all natural numbers $\leq k$ \\
IS: Now we want to prove that the claim is true when n=k+1. \\ Consider the largest fibonnaci number less thank k+1 called $f_{1}$. \\ We know that $f_{1}+f_{i+1}=f_{2} > k+1$ which implies that $k+1-f_{1} < f_{i-1}$ \\ Now since, we already assumed in the induction hypothesis that we can produce any natural number less than k using the sum of distint, non consecutive fibonnaci numbers, this implies that $k+1-f_{i-1}$ falls under the induction hypothesis and satisfies the constraint that they cannot be consecutive because $f_{i-1}$ is not used. THus we have proven the claim 

\item we will prove by induction on n \\ Base Case: n=2 we have two questions: 1) is there a direct road from $A \to B$? 2) is there a direct road from $B \to A$? thus we have $\leq 3(n-1)$ = 3 questions \\
IH: assume that the claim is true for n cities, we want to prove that it is true for n+1 cities. \\ 
IS: Now when we have n+1 cities, we remove one and now we have n cities. It is assumed that we can solve the problem with (3n-1) questions, so when we add a city, we now get 3(n+1-1) = 3n questions questions. But we have already assumed that we know whether there is a deadend city or not so we must split it up into cases. \\

Case 1: Dead end city $D$ existed for n cities, meaing there are (n-1) cities besies D and our newly added city (n+1) called X. So besides D, there are n cities now. \\ Questions: 1) is there a road going from D to A? if yes, D is not a Deadend. if no, D is still Deadend. 2) if yes, then we must ask if there is a road going from A to D. if yes, there is no deadend, if no, A could be dead end, but we must test this for (n-1) cities and therefore we must ask a total of (n-1) questions that ask is there a road from A to C for all cities C. Total amount of questions asked in Case 1 is (n+1).\\

Case 2: There is no deadend \\ A could be deadend, but we have to ask n questions: Is there a road from A to C for all cities C, but we already ask this in Case 1. So we can determine if there is a new city in under 3(n-1) questions thus proving the claim.

\item $\frac{15}{56}$ \\ The sample space consists of all the series ending in 4 games plus all the games ending in 5, 6, and 7. This can be represente as ${4 \choose 4}+{5 \choose 4}+{6 \choose 4}+{7 \choose 4}$ = 56 but we must multiply by 2 to include those scenarios in which either teams win. Now to find the probability of a team winning in 6 games we need to do $\frac{2*{6 \choose 4}}{112}$ which equals $\frac{15}{56}$

\item the probability that you can go from A to C is determined by the probability of going from A to C directly plus the probability of going from A to C through B. \\ p[A to C] = $(1-p)$ \\ p[A to B to C] = $(1-p)(1-p)$ so we just add the two together to get \\ p[A to C] = $(1-p)+(1-p)^2$

\item The sample space = 100,000 numbers. Now to find out how many numbers would yield us a number divisible by 4, 6, or 9, we must use the principle of inclusion and exclusion. \\ 
$\frac{100,000}{4}+\frac{100,000}{6}+\frac{100,000}{9}-\frac{100,000}{24}-\frac{100,000}{54}-\frac{100,000}{36}+\frac{100,000}{216}$ = $\frac{44445}{100000}$

\end{enumerate}
\end{document}