# Homework 8w

Author

Geoffrey Bostany

License

Creative Commons CC BY 4.0

Abstract

homework 8w

Share your thoughts on the Overleaf Template Gallery!

Author

Geoffrey Bostany

License

Creative Commons CC BY 4.0

Abstract

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}
```