I have 4 questions, 3 of which I typed up my proposed solutions for. I need help with the 4th problem still.
$1.)$ A sequence is defind by letting $b_0=5$ and $b_k=4+b_{k-1}$ for all integers $k \geq 1$. Show that $b_n \gt 4n$ for all integers $n \geq 0$.
The way to do this is by induction. Notice that the base case of $n=0$ holds because $b_0=5$ and so $b_0 = 5 \geq n*0=0$.
Our inductive hypothesis will be that this statement holds for when $n=k$. We now wish to show that our statement is true when $n=k+1$, and we will use our inductive hypothesis to do so. This statement being true when $n=k+1$ means that:
$b_{k+1} \gt 4{(k+1)}$. So this is the inequality that we hope to prove is true.
Notice that $b_{k+1} = 4 + b_k$,
so the inequality that we are hoping to prove to be true can be restated as $4 + b_k$ $\gt 4{(k+1)}$
By our inductive hypothesis, $b_k$ $\gt 4{k}$
so $b_k + 4$ $\gt 4k+4 = 4{(k+1)}$
So putting it all together,
$b_{k+1} = b_k + 4$ $\gt 4k+4 = 4{(k+1)}$
Thus our statement is true in the case of $n=k+1$. Thus the statement is true, proof via induction.
$2.)$ How many integers must you pick so at least two of them have the same remainder when divided by 15? The answer is 15. Let's now understand why.
If $n$ is an integer, then we can write $n$ as $n= 15*a + b$ where $0 \leq b \lt 15$ by the division algorithm. Notice that this is just division, we have $n$ divided by $15$ has a quotient equal to $a$ and with a remainder of $b$. The point is, every integer $n$, when divided by $15$, will have a remainder of either $0,1,2,3,4,5,6,7,8,9,10,11,12,13,$ or $14$. Furthermore, given one of these integers 0-14, we can find an integer such that when divided by 15 it has that said remainder. So we can choose 15 numbers that all have different remainders when divided by 15, but as soon as we had a 16th integer than that number must have the same remainder as the original 15 that we chose.
$3.)$ For all sets, is $X \times \emptyset = \emptyset$?
There answer to this is yes. If we have sets $A$ and $B$ then their cross product is $A \times B$, and an arbitary element from this set is of the form $(a,b)$ where $a \in A$ and $b \in B$. So in the case of $X \times \emptyset$ an element would look like $(x,y)$ where $x \in X$ and $y \in \emptyset$... but there is no $y \in \emptyset$ because $\emptyset$ is the empty set! Therefore $A \times \emptyset = \emptyset$
$4.)$ if $g(x)$ is $O(f(x))$ must it be true that $f(x)$ is $\Omega (g(x))?$ I have no clue how to do this question, help is appreciated!!