Explore Discrete Math Examples

Proving Modus Tollens with Logical Equivalences
How would you prove modus tollens is a tautology using logical equivalences?
So far, I have reduced it using implication logical equivalence, demorgan's law, and double negation and got it to the form of:
q or $(pand\sim <!--\; \sim \; -->q)ornotp=T$
From there, I can't figure out how to make it always imply T. Because I tried it distributing it, but then it became something like
(q or p) and $(qor\sim <!--\; \sim \; -->p)or\sim <!--\; \sim \; -->p$ which should be become (q or p) and $\sim <!--\; \sim \; -->p$ but that doesn't result in a tautology. What mistake am I making?

Inductively prove $1+\frac{1}{2}+\frac{1}{4}+\cdots <!--\; \cdots \; -->+\frac{1}{2^n}=2-<!--\; -\; -->\frac{1}{2^n}$
Inductively prove that the formula holds for all $n\in <!--\; \in \; -->\mathbb{N}$:
$$1+\frac{1}{2}+\frac{1}{4}+\cdots <!--\; \cdots \; -->+\frac{1}{2^n}=2-<!--\; -\; -->\frac{1}{2^n}.$$
What I have so far:
base: $n=1$:
$$1+\frac{1}{2}=2-<!--\; -\; -->\frac{1}{2}=1.5$$
inductionstep: $n=k$:
$$1+\frac{1}{2}+\cdots <!--\; \cdots \; -->+\frac{1}{2^k}=2-<!--\; -\; -->\frac{1}{2^k}$$
inductionhypothesis: $n=k+1$:
$$1+\frac{1}{2}+\cdots <!--\; \cdots \; -->+\frac{1}{2^k+1}=1+\frac{1}{2}+\cdots <!--\; \cdots \; -->+\frac{1}{2^k}+\frac{1}{2^{(}k+1)}=(2-<!--\; -\; -->\frac{1}{2})+\frac{1}{2^k+1}$$
This is where I am stuck and not sure what to do next.

Suppose that L(x,y) means that x loves y. I am to write symbolically, "For every person that loves someone, there exists a unique person that loves them" I feel like there are a hundred different ways to answer this question! The closest I can get is AxEyL(x,y) E!cL(c,x) I feel as if there should be an amplification arrow in between the two though..

How can I simplify the expression $k<\frac{n}{n^{1/2}+n^{1/4}+1/2}$ using the big O notation?
I'm learning about big O notation and I'm having problems with this exercise. Let be n and k positive integers, how can I simplify the expression $k<\frac{n}{n^{1/2}+n^{1/4}+1/2}$ using a dominant power of n and and a big O of a menor power of n. This is what I have done:
$k<\frac{n}{n^{1/2}+n^{1/4}+1/2}$, we know that for some positive C we have that $-<!--\; -\; -->C{n}^{1/4}\le <!--\; \le \; -->n^{1/4}+1/2\le <!--\; \le \; -->C{n}^{1/4}$, then $k<\frac{n}{n^{1/2}-<!--\; -\; -->O(n^{1/4})}$, so $k<\frac{n^{1/2}}{1-<!--\; -\; -->O(n^{-<!--\; -\; -->1/4})}$. Then $k(1-<!--\; -\; -->O(n^{-<!--\; -\; -->1/4}))<n^{1/2}$, so $k-<!--\; -\; -->kO(n^{-<!--\; -\; -->1/4})<n^{1/2}$.
I want to change the k in the expression $-<!--\; -\; -->kO(n^{-<!--\; -\; -->1/4})$ in terms of some power o n and I have been struggling with that. Any one have any advice?

Time needed to decrypt a message $r=p\times <!--\; \times \; -->q$, where r is the message.
If we can represent a secret message by a large prime number p, we can transmit over the network the number $r=p·q$, where $q>p$ is another large prime number that acts as the encryption key and r can take 100 bits.
Question: What is the worst-case time complexity of the above algorithm?
Since the input to the algorithm is just one large number r, assume that the input size n is the number of bytes needed to store r, that is, $n=\frac{{\log }_2<!--\; \; -->n}{8}$, and that each division takes time O(n). So we need $\frac{r}{p}$ divisions in order to get the encrypted message. Now the questions is how we can calculate the complexity of the algorithm where we need to guess each and every single possibility, thus I said we need $\frac{r}{p}$ divisions.
$$\frac{r}{p}=\frac{r}{2^{100}}divisions$$
Problem: I assume the complexity in the question is referring to number of divisions or both divisions and space? So, the question is now, I am not sure why the complexity is $O(n\times <!--\; \times \; -->2^{4n})$?

Consider the following problem. Take an nxn table A with entries $\pm <!--\; \pm \; -->1$. A permitted move is multiplying any row or column by -1. How many nxn tables exist that can be transformed to a table containing only 1s?
I've done questions like this where I'm given an initial table and prove that the operation can't be done. Those proofs often rely on invariants. For instance, the product of any row or column is invariant after applying one of the permitted moves. Also, the product of any 2x2 squares within the table remains invariant. Using those two facts I've been able to prove some tables can never be transformed to only contain 1s. But not sure I can use invariants for this more general question.
Intuition tells me that the only permitted nxn tables of this form are the initial table containing all 1s or permutations of tables containing an entire row or column of -1s which can be later transformed into a table of only 1s. I'm not sure how to prove this, I'm not sure if I can use invariants since this is for a general n.
Would anyone have any suggestions as to how to move forward with this question and how can I count the number of nxn matrices in question?

Discrete Math composition functions
Give examples of sets X, Y, Z and functions $f:X\to <!--\; \to \; -->Y$, $g:Y\to <!--\; \to \; -->Z$, so that the composition $g\circ <!--\; \circ \; -->f:X\to <!--\; \to \; -->Z$ is a bijection, although neither f or g it is.

Discrete Math - onto, 1-1 functions
Let $S=\{3,B\}$
Give an example of a function $f:S\times <!--\; \times \; -->S\to <!--\; \to \; -->S$ that is onto.
Give an example of a function $g:S\to <!--\; \to \; -->S\times <!--\; \times \; -->S$ that is 1-1.
Give an example of a function $h:P(S)\to <!--\; \to \; -->S\times <!--\; \times \; -->S$ that is 1-1 and onto.
Trying to revise for exam, but simply cannot understand 1-1 and onto functions.

Discrete math counting question help
100 students from each of the 3 schools form a line. For each student (except the 1st and the last), the two neighboring students must be from 2 schools different than his/her school. The 1st and last student in the line must have his/her neighboring student from a school different than his/her school. How many ways are there to form such a line of 300 students?

Discrete Math True or False
1. $\mathcal{P}(A\setminus <!--\; \setminus \; -->B)=\mathcal{P}(A)\setminus <!--\; \setminus \; -->P(B)$
These are power sets. False.
2. If G is bipartite, then the complement of G is disconnected.
False.
3. Suppose F and G are families of sets with the property that for each $A\in <!--\; \in \; -->F$ there exists a $B\in <!--\; \in \; -->\mathcal{G}$ such that $A\subseteq <!--\; \subseteq \; -->B$. Then $\cap <!--\; \cap \; -->\mathcal{F}\subseteq <!--\; \subseteq \; -->\cap <!--\; \cap \; -->\mathcal{G}$.
False
4. Let x be a vertex of a connected graph G. Then x is a cut vertex of G if and only if x is not a leaf of any spanning tree of G.
True.

How many 5-card hands have at least two cards with the same rank?
This is a question from Zybooks Exercise 5.7.2: Counting 5-card hands from a deck of standard playing cards. I just can't wrap my head around the answer. If there is anyone that can explain this in English, that would be greatly appreciated.
How many 5-card hands have at least two cards with the same rank? Apparently the answer to this is $(\genfrac{}{}{0ex}{}{52}{5})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{13}{5})4^5$.
I see that we are using the complement rule here. I get $(\genfrac{}{}{0ex}{}{52}{5})$ denotes all the 5-card hands in a 52-card deck, but I don't see why we are subtracting $(\genfrac{}{}{0ex}{}{13}{5})4^5$.

Combinatorics (discrete math course help)
2 questions:
1. How many odd 14 digit numbers can you compose of ten 1's and four 2's such that in between every pair of 2's there are at least two 1's?
Here I could have 4 or 5 spaces for the 1's to be in between, is the maximum 5 enough? So $C(5+10-<!--\; -\; -->3,5-<!--\; -\; -->1)$?
2. In how many ways can you arrange 5 red balls, 5 yellow balls and 2 blue balls (where balls of the same color are considered identical) such that the ball on the right edge will be red and there are not two red balls next to each other?
Total ways to arrange the balls: C(12,3).
2 options that the ball on the right is not red. so far $C(12,3)-<!--\; -\; -->2$. I'm not sure whats the right to account for red balls not being next to each other.

Discrete math induction proof
Statement: For all integers n≥5 we have 2n≥n2.
Proof: Induction over n. Introduce the name A(n) for the statement $2^n\ge <!--\; \ge \; -->n^2$. We shall prove, by mathematical induction that $\mathrm{\forall <!--\; \forall \; -->}n\ge <!--\; \ge \; -->5:A(n)$.
1. A(n) and test with 5 so that $A(5):2^5\ge 5^2⟹<!--\; ⟹\; -->32\ge 25$ (true)
2. Assume A(p) so that we have $A(p):2^p\ge <!--\; \ge \; -->p^2$ and we want to prove $A(p+1):2^{p+1}\ge <!--\; \ge \; -->(p+1{)}^2$.
$2^{p+1}\ge <!--\; \ge \; -->(p+1{)}^2⟺<!--\; ⟺\; -->2\cdot <!--\; \cdot \; -->2^p\ge p^2+2p+1$, with the assumption $2^p\ge <!--\; \ge \; -->p^2$ we get $2p^2\ge p^2+2p+1$, it is here where i dont know how to continue to prove the statement.

Model Theory Question for Predicate Logic in van Dalen's Logic and Structure
Let L be a language without identity and with at least one constant.
Let $\mathrm{\sigma <!--\; \sigma \; -->}=\mathrm{\exists <!--\; \exists \; -->}x1···xn\mathrm{\varphi <!--\; \varphi \; -->}(x1,...,xn)$, where $\mathrm{\sigma <!--\; \sigma \; -->}$ is a formula in predicate logic.
Let $\mathrm{\exists <!--\; \exists \; -->}=\{\mathrm{\varphi <!--\; \varphi \; -->}(t1,...,tn)|t_i$ closed in L}, where $\mathrm{\varphi <!--\; \varphi \; -->}$ is quantifier free.
I want to show that:
(i) $\models \mathrm{\sigma <!--\; \sigma \; -->}\iff <!--\; \iff \; -->$ each structure A is a model of at least one sentence in Σ. (Hint: for each A, look at the substructure generated by $\varnothing$.)
(ii) Consider $\sum <!--\; \sum \; -->$ as a set of propositions. Show that for each valuation v (in the sense of propositional logic) there is a model A such that $v(\mathrm{\varphi <!--\; \varphi \; -->}(t1,...,tn))=$ the interpretation of $\mathrm{\varphi <!--\; \varphi \; -->}(t1,...,tn)$ in A, for all $\mathrm{\varphi <!--\; \varphi \; -->}(t1,...tn)\in <!--\; \in \; -->\sum <!--\; \sum \; -->.$

Discrete Math - Relations and Matrix Representations
Are these answers correct? Do we assume p is created from S twice? Binary relation p on the set $S=\{a,b,c,d,e\}$ is defined as: $p=\{(a,c),(a,e),(b,a),(e,d)\}$. 
1. What is the matrix representation of p?
2. Is p a reflexive relation?
Please explain. 
(1.) Would the matrix representation of p be following: a 1 placed at the intersections of (a,c),(a,e),(b,a),(e,d) and the rest zeros where $a-<!--\; -\; -->e$ is listed for columns and rows?
(2.) p is not a reflexive relation because for every element a in A, there is not an ordered pair (a,a) in the relation.

Finding the intersection of $A\times <!--\; \times \; -->B$ and $B\times <!--\; \times \; -->A$
Let $A=\{x,3\}$ and $B=\{y,3,z\}$. List all of the elements in the set $(A\times B)\cap (B\times A)$.
Is the Cartesian product of the two sets listed above a set of 2-ordered tuples? And the intersection is just the elements that $A\times <!--\; \times \; -->B$ has in common with $B\times <!--\; \times \; -->A$? That is,
$$\begin{array}{rl}A\times <!--\; \times \; -->B& =\{x,3\}\times <!--\; \times \; -->\{y,3,z\}=\{(x,y),(x,3),(x,z),(3,y),(3,3),(3,z)\}\\ B\times <!--\; \times \; -->A& =\{y,3,z\}\times <!--\; \times \; -->\{x,3\}=\{(y,x),(y,3),(3,x),(3,3),(z,x),(z,3)\}\end{array}$$
giving $(A\times <!--\; \times \; -->B)\cap (B\times <!--\; \times \; -->A)=\{(3,3)\}$
Is there some higher order of precedence? And I assume order matters, right?

On each of the 22 work days in a particular month, every employee of a start-up venture was sent a company communication. If a total of 4730 company communications were sent, how many employees does the company have, assuming that no staffing changes were made that month?
From the Discrete math book :
If the finite set A is the union of n pairwise disjoint subsets each with d elements, then $n=|A|/d$
Using this formula from the book, I calculated this to be $4730/22=215$
Can you please confirm if this is correct and if my understanding is right, because the book mentions this to be a hard problem and I am not sure if I am missing something?

Indexing a set of objects with a symmetry or antisymmetry property
Suppose I have a collection of objects $\{X(i,j){\}}_{i,j=1}^n$ (which could be anything - numbers, functions, matrices, …) indexed by $1\le <!--\; \le \; -->i,j\le <!--\; \le \; -->n$, such that the following holds:
$$X(i,j)=X(j,i).$$
Up to the above constraint, all of the objects are different. If I want to index every object, such that no equal object is indexed more than once, I can impose the condition that $i\le <!--\; \le \; -->j$ in my indexing.
My question is, how do I generalize this to sets of objects with more than two indices. For example, if I have {X(i,j,k)} such that
$$X(i,j,k)=X(k,j,i),$$
or {X(i,j,k,l)} such that
$$X(i,j,k,l)=X(l,k,j,i),$$
what condition on the indices can I impose so that I index each non-equal object exactly once?

Modular arithmetic, Discrete math.
Let m be a prime number and $r\in <!--\; \in \; -->\mathbb{N}$.
We'll define $x=(x_1,...,x_r)y=(y_1,...,y_r)$ such that $x_i\ne <!--\; \ne \; -->y_i\mathrm{\forall <!--\; \forall \; -->}1\le <!--\; \le \; -->i\le <!--\; \le \; -->r$
Also, let $(a_1,...a_r)$ be a sequence of numbers such that $a_i\in <!--\; \in \; -->\mathbb{Z}$, specifically $0\le <!--\; \le \; -->a_i\le <!--\; \le \; -->m-<!--\; -\; -->1\mathrm{\forall <!--\; \forall \; -->}1\le <!--\; \le \; -->i\le <!--\; \le \; -->r$.
How many sequences $(a_1,...a_r)$ exist such that $(\underset{i=1}{\overset{r}{\sum <!--\; \sum \; -->}}{a}_i{x}_i)modm=(\underset{j=1}{\overset{r}{\sum <!--\; \sum \; -->}}{a}_j{y}_j)modm$
I understand the concept of the question, I wrote the above equation as $(\underset{i=1}{\overset{r}{\sum <!--\; \sum \; -->}}{a}_i(x_i-<!--\; -\; -->y_i))modm=0$
Obviously $(x_i-<!--\; -\; -->y_i)$ can be anything but 0, however $(x_i-<!--\; -\; -->y_i)modm$ can be 0.

Discrete Math On inductions
Show that the sequence defined by the formula $a_n=n+3$, satisfies the recurrence relation $$a_n=2a_{n-<!--\; -\; -->1}-<!--\; -\; -->a_{n-<!--\; -\; -->2}$$, for all $n\ge <!--\; \ge \; -->2$.
I know this is a induction problem and I think I have to set $n=n+1$ but I'm not sure that how would I show the recurrence relation between them.