Explore Discrete Math Examples

Composition of Matrix relation
I am unsure if this exercise is possible to do, could anyone tell me if I am correct or not?
We have DOMAIN $\{1,2,3\}$ and RANGE $\{1,2,3,4\}$ and relation $R=\{(1,2),(2,3),(3,4)\}$.
The exercise say to find $R^2$.
I have tried two way to find this.
1. Matrix composition. Here i cam across the problem that you cannot compose a $3\times <!--\; \times \; -->4$ matrix with another $3\times <!--\; \times \; -->4$.
2. Compose the relations themselves what i get is $\{(1,3),(2,4),(3,?)\}$
I cant see how i can find the 4 to replace ?

Proof verification for proof by contraposition
prove using contraposition that if a and b are integers:
$a^2-<!--\; -\; -->4b-<!--\; -\; -->2\ne <!--\; \ne \; -->0$
So the contrapositive:
$a^2-<!--\; -\; -->4b-<!--\; -\; -->2=0$ implies that at least one of either a or b are not integers
Working from the above, I got: $a^2=4b+2$
$a^2=2(2b+1)$
If both a and b are integers, $2(2b+1)$ is a perfect square.
In other words: $\sqrt{2(2b+1)}=k$
Where k is an integer
I also realised that $2b+1$ is an odd number so:
$k=\sqrt{2}\sqrt{2b+1}$
I ended my proof by saying that since $2b+1$ is odd, it does not have a multiple of 2 so k will always have multiple or $\sqrt{2}$ which means that it cannot be an integer.

If $x^3-<!--\; -\; -->x>0$, so $x>-<!--\; -\; -->1$. How do I prove that by contrapositive?
My attempt:
$Q⟹<!--\; ⟹\; -->P$, by contrapositive we have: $\mathrm{\neg <!--\; \neg \; -->}Q⟹<!--\; ⟹\; -->\mathrm{\neg <!--\; \neg \; -->}P$, so, if $x<-<!--\; -\; -->1$, $x^3-<!--\; -\; -->x<0$.

What classes of graphs result from $\stackrel{¯<!--\; ¯\; -->}{T}$?
I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More formally, let $T=(V,E)$ be an n-vertex tree with vertex set V and edge set E. Are there known results on the classes of graphs defined by $\stackrel{¯<!--\; ¯\; -->}{T}$?
There are two trivial cases. If $T=S_n$, i.e., is a star tree (one single vertex has degree $n-<!--\; -\; -->1$ and the other vertices have degree 1), we have that $\stackrel{¯<!--\; ¯\; -->}{S_n}=\{v\}\cup <!--\; \cup \; -->K_{n-<!--\; -\; -->1}$, i.e., $\stackrel{¯<!--\; ¯\; -->}{S_n}$ is a graph with an isolate vertex (degree 0) and a $(n-<!--\; -\; -->1)$ vertex clique. I've got the feeling that $\stackrel{¯<!--\; ¯\; -->}{P_n}$ (where $P_n$ is an n-vertex path graph) has a precise characterization but I can't put a name to it.
If there are no (or few) results about general T, can we say something about $\stackrel{¯<!--\; ¯\; -->}{T}$ if T belongs to a class of trees, for example caterpillar trees (trees in which the removal of all leaves produces a path graph), lobster trees (trees in which the removal of all leaves produces a caterpillar tree), ...?
Any help will be appreciated. Thank you.

Is there an algorithm to define a recursive function such that consecutive terms approach any arbitrary constant?
The Fibonacci sequence is defined by the recursive function, $f(n)=f(n-<!--\; -\; -->1)+f(n-<!--\; -\; -->2)$. Consecutive terms in this sequence approach the constant, $\frac{1+\sqrt{5}}{2}$. Is there an algorithm that produces recursive functions such that $f(n)/f(n-<!--\; -\; -->1)$ approaches any arbitrary algebraic constant?

Solving the recurrence $b_n=4b_{n-1}-4b_{n-2}$
I have the answer to the following question.
Solve the following recurrence equation with the given initial values: $b_n=4b_{n-1}-4b_{n-2}$. Initial values: $b_0=3$, $b_1=10$.
I am looking for an explanation. The answer is: $3\cdot <!--\; \cdot \; -->2^n+n{2}^{n+1}$. How did it get to this answer? Here is where I am at: $b_n-<!--\; -\; -->4b_{n-<!--\; -\; -->1}+4b_{n-<!--\; -\; -->2}=0$
$x^2-<!--\; -\; -->4x+4=0⟹<!--\; ⟹\; -->x=2$.

P poset: $J\subseteq <!--\; \subseteq \; -->P$ is join-dense iff $\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->P$, $x=(\downarrow <!--\; \downarrow \; -->x\cap <!--\; \cap \; -->J)$

Big intersection operation
$\mathrm{\varnothing <!--\; \varnothing \; -->}\ne <!--\; \ne \; -->A\subseteq <!--\; \subseteq \; -->B\Rightarrow <!--\; \Rightarrow \; -->\bigcap <!--\; \bigcap \; -->B\subseteq <!--\; \subseteq \; -->\bigcap <!--\; \bigcap \; -->A.$
In each case, the proof is straightforward. For example, in the last case, we assume that every member of A is also a member of B. Hence if $x\in <!--\; \in \; -->\bigcap <!--\; \bigcap \; -->B$, i.e., if x belongs to every member of B, then a fortiori x belongs to every member of the smaller collection A. And consequently $x\in <!--\; \in \; -->\bigcap <!--\; \bigcap \; -->A$.
I wonder if the last part is really a proof. It is okay to assume $x\in <!--\; \in \; -->\bigcap <!--\; \bigcap \; -->B$ and arrive at $x\in <!--\; \in \; -->\bigcap <!--\; \bigcap \; -->A$. But can I use this reasoning "then a fortiori x belongs to every member of the smaller collection" in a proof exercise? It looks like just using intuition (it does not seem rigorous).

How do you prove
$\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\displaystyle \frac{1}{(2n-<!--\; -\; -->1{)}^s}}={\displaystyle \frac{(2^s-<!--\; -\; -->1)\mathrm{\zeta <!--\; \zeta \; -->}(s)}{2^s}}$
where $s>1$

How to show that the complement of Cartesian product of two non-empty sets is not the same as the Cartesian product of their complements?
$(A\times <!--\; \times \; -->B{)}^C=(A^C\times <!--\; \times \; -->B^C)\cup <!--\; \cup \; -->(A^C\times <!--\; \times \; -->B)\cup <!--\; \cup \; -->(A\times <!--\; \times \; -->B^C)$
I wanted to do it like this:
$A\times <!--\; \times \; -->B=\{(a,b)\in <!--\; \in \; -->A\times <!--\; \times \; -->B|a\in <!--\; \in \; -->A\wedge <!--\; \wedge \; -->b\in <!--\; \in \; -->B\}$
Taking complement, $\stackrel{¯<!--\; ¯\; -->}{A\times <!--\; \times \; -->B}=\{(a,b)\notin <!--\; \notin \; -->A\times <!--\; \times \; -->B|a\notin <!--\; \notin \; -->A\vee <!--\; \vee \; -->b\notin <!--\; \notin \; -->B\}$
Because $(a,b)\notin <!--\; \notin \; -->A\times <!--\; \times \; -->B$ prevents me from going anywhere, I chose to do:
Let $A\times <!--\; \times \; -->B\subseteq <!--\; \subseteq \; -->X\times <!--\; \times \; -->Y$
Then, $A\times <!--\; \times \; -->B=\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|a\in <!--\; \in \; -->A\wedge <!--\; \wedge \; -->b\in <!--\; \in \; -->B\}$ and $\stackrel{¯<!--\; ¯\; -->}{A\times <!--\; \times \; -->B}=\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|a\notin <!--\; \notin \; -->A\vee <!--\; \vee \; -->b\notin <!--\; \notin \; -->B\}$
But I'm unsure about the correctness of what I did from here.
$\stackrel{¯<!--\; ¯\; -->}{A\times <!--\; \times \; -->B}=\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|(a\notin <!--\; \notin \; -->A\wedge <!--\; \wedge \; -->b\notin <!--\; \notin \; -->B)\vee <!--\; \vee \; -->(a\notin <!--\; \notin \; -->A\wedge <!--\; \wedge \; -->b\in <!--\; \in \; -->B)\vee <!--\; \vee \; -->(a\in <!--\; \in \; -->A\wedge <!--\; \wedge \; -->b\notin <!--\; \notin \; -->B)\}$
Therefore, $\stackrel{¯<!--\; ¯\; -->}{A\times <!--\; \times \; -->B}=\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|(a\notin <!--\; \notin \; -->A\wedge <!--\; \wedge \; -->b\notin <!--\; \notin \; -->B)\}\cup <!--\; \cup \; -->\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|(a\notin <!--\; \notin \; -->A\wedge <!--\; \wedge \; -->b\in <!--\; \in \; -->B)\}\cup <!--\; \cup \; -->\{(a,b)\in <!--\; \in \; -->X\times <!--\; \times \; -->Y|(a\in <!--\; \in \; -->A\wedge <!--\; \wedge \; -->b\notin <!--\; \notin \; -->B)\}$ which gives
We know $A\times <!--\; \times \; -->B\subseteq <!--\; \subseteq \; -->A\times <!--\; \times \; -->B$.
Hence, $\stackrel{¯<!--\; ¯\; -->}{A\times <!--\; \times \; -->B}=(\stackrel{¯<!--\; ¯\; -->}{A}\times <!--\; \times \; -->\stackrel{¯<!--\; ¯\; -->}{B})\cup <!--\; \cup \; -->(\stackrel{¯<!--\; ¯\; -->}{A}\times <!--\; \times \; -->B)\cup <!--\; \cup \; -->(A\times <!--\; \times \; -->\stackrel{¯<!--\; ¯\; -->}{B})$.
"Derive" instead of "prove" because I don't need to prove the equivalence per se. I'm just trying to see how the LHS can lead to the RHS. I should've been more careful about the wording

Multiplicative inverse of $[9{]}_{23}$
I'm new to modular arithmetic and this has been very confusing for me. I know that in order for an element $[a{]}_m$ to be invertible, the GCD of (a,m) has to be 1.
I have the element $[9{]}_{23}$.
Now, the GCD of those two numbers is 1. We form the Diophantine equation
$9x+23y=1,$, and after performing the extended Euclidean algorithm we have that $1=2\cdot <!--\; \cdot \; -->23-<!--\; -\; -->5\cdot <!--\; \cdot \; -->9$ which is true. The solution for x is $x={\mathrm{\lambda <!--\; \lambda \; -->}}_{1}b+t\cdot <!--\; \cdot \; -->a_2$ where ${\mathrm{\lambda <!--\; \lambda \; -->}}_1$ is the first coefficient in the euclidean algorithm and equal to 2, b is the right side of the equation 1, and $a_2$ is the second coefficient in the equation, which is 23.
This gives me $x=2+23t$ for any integer t.
I need to look for the typical represent, so $x\in <!--\; \in \; -->[0,23]$. We can achieve this by plugging $t=0$, and thus $x=2$.
However, $[9{]}_{23}\cdot <!--\; \cdot \; -->[2{]}_{23}\ne <!--\; \ne \; -->[1{]}_{23}$.
Where did I go wrong? The only thing my workbook did different was they switched the places in the euclidean algorithm $1=-<!--\; -\; -->5\cdot <!--\; \cdot \; -->9+2\cdot <!--\; \cdot \; -->23$ which gave them a solution that checks out. They got $x=-<!--\; -\; -->5+23t$, and for $t=1$ they got $x=18$, which is the multiplicative inverse.
This made me curious where I went wrong. In my mind, the only thing I did differently was switch the places of the two operands in the euclidean algorithm.

Each group gets 6 out of 18 questions (3 easy, 15 hard), probability all groups have one easy question
In a course, students form three groups. Each group is assigned 6 questions, chosen at random, without replacement, from a set of 18 questions. From these 18 questions, 3 are easy and 15 are hard. What is the probability all groups have one easy question?
Attempt. Let $E_i$ be the event group i has at least one easy question. The desired event is $E_1{E}_2{E}_3$ and using complements and inclusion/exclusion:
$\mathbb{P}(E_1{E}_2{E}_3)=1-<!--\; -\; -->\mathbb{P}(E_1^{\prime }\cup <!--\; \cup \; -->E_2^{\prime }\cup <!--\; \cup \; -->E_3^{\prime })=1-<!--\; -\; -->[3\mathbb{P}(E_1^{\prime })-<!--\; -\; -->3\mathbb{P}(E_1^{\prime }{E}_2^{\prime })+\mathbb{P}(E_1^{\prime }{E}_2^{\prime }{E}_3^{\prime })]$
(since $\mathbb{P}(E_i^{\prime })=\mathbb{P}(E_j^{\prime })$ and $\mathbb{P}(E_i^{\prime }{E}_j^{\prime })=\mathbb{P}(E_k^{\prime }{E}_m^{\prime })$).
Also: $\mathbb{P}(E_1^{\prime })=\frac{(\genfrac{}{}{0ex}{}{3}{0})(\genfrac{}{}{0ex}{}{15}{6})}{(\genfrac{}{}{0ex}{}{18}{6})},$,
$\mathbb{P}(E_1^{\prime }{E}_2^{\prime })=\frac{(\genfrac{}{}{0ex}{}{3}{0})(\genfrac{}{}{0ex}{}{15}{12})}{(\genfrac{}{}{0ex}{}{18}{12})},$
$\mathbb{P}(E_1^{\prime }{E}_2^{\prime }{E}_3^{\prime })=0.$
Do you see any flaw in the above argument?

Prove that no graph has exactly 2 spanning trees.
This question is why I must go second time to the final exam in discrete mathematics.
The original question was:
For which n exists a graph with n spanning trees?
I know, that for $n>2$ there exists a graph with n spanning trees, because if we take $C_3$, which is a cycle with 3 vertices, it has exactly 3 spanning trees. Cycle on 4 vertices has 4 spanning trees and so on. I know that if a graph is not connected, than it has 0 spanning trees, and if I have a graph on 1 vertex, it has exactly 1 spanning tree.
So the question remains, how do I prove, that no graph exists, which has exactly 2 spanning trees.

If a function f(x) is constant complexity $f(x)=O(1)$, describe C and k.
If a function f(x) is constant complexity $f(x)=O(1)$, describe C and k.
This needs to be described in terms of the relation of C and k.
There exists constants C and k such that $C|f(x)|\le <!--\; \le \; -->|1|$, for all $x>k$.
The above cannot be true because using the explanation from the book of discrete math:
f(x) is O(g(x)) if there are constants C and k such that $\mathrm{\forall <!--\; \forall \; -->}x>k,|f(x)|\le <!--\; \le \; -->C|g(x)|.$.
So if $f(x)=O(1)$, then it would mean $O(1)\le <!--\; \le \; -->C|g(x)|$, or $C|g(x)|\ge <!--\; \ge \; -->O(1)$.
Instead the below statement is true.
There exists constants C and k such that $C|f(x)|\ge <!--\; \ge \; -->|1|$ for all $x>k$.

Formal proof that a is congruent to (a mod m) (mod m)
Intuitively it is quite easy to see why
$a\equiv <!--\; \equiv \; -->(amodm)(\mathrm{mod}m).$
When you divide a by m you get a remainder in the range $0,\dots <!--\; \dots \; -->,m-<!--\; -\; -->1.$. When you divide the remainder by m again, you get the same number again as the remainder, except that this time the quotient is 0.

Simple question about number theory in CLRS book
This is theorem 11.5 from CLRS book. Suppose $a\in <!--\; \in \; -->{\mathbb{Z}}_p^{\ast <!--\; \ast \; -->},b\in <!--\; \in \; -->{\mathbb{Z}}_p$.
Consider two distinct keys k and l from ${\mathbb{Z}}_p$, so that $k\ne <!--\; \ne \; -->l$. For a given hash function $h_{ab}$ we let
$r=ak+b\mathrm{mod}p$
$s=al+b\mathrm{mod}p$
We first note that $r\ne <!--\; \ne \; -->s$. Why? Observe that
$r-<!--\; -\; -->s\equiv <!--\; \equiv \; -->a(k-<!--\; -\; -->l)(\mathrm{mod}p).$
I'm not very well familiar with Number Theory, so my question is why $r-<!--\; -\; -->s\equiv <!--\; \equiv \; -->a(k-<!--\; -\; -->l)(\mathrm{mod}p)$ is correct?

A question on inequality equivalence
I'm doing a textbook question and I'm stuck in the very last end...
I got the following function on S:
$f(S)=S-<!--\; -\; -->\frac{q(1-<!--\; -\; -->q^S)}{p}+q^{S}c$, where $p:=1-<!--\; -\; -->q$ and $0<p,q<1$.
Now the first forward difference of f(S), so $\mathrm{\Delta <!--\; \Delta \; -->}(S):=f(S+1)-<!--\; -\; -->f(S)$ is $\mathrm{\Delta <!--\; \Delta \; -->}(S)=1-<!--\; -\; -->q^S(pc+q)$ and this function is increasing in S.
Now I need to find the value of S that satisfies $\mathrm{\Delta <!--\; \Delta \; -->}(S)\ge <!--\; \ge \; -->0$.
We can then write an inequality:
$q^S\le <!--\; \le \; -->\frac{1}{(pc+q)}$
But now when I want to look for S, we can take logarithms and find:
$S\le <!--\; \le \; -->\frac{-<!--\; -\; -->ln(pc+q)}{ln(q)}$
But the textbook says that the equivalent inequality to $q^S\le <!--\; \le \; -->\frac{1}{(pc+q)}$ is: $S\ge <!--\; \ge \; -->\frac{ln(pc+q)}{-<!--\; -\; -->ln(q)}$
Why is this?
They also say in the question: "using the fact of $\ln <!--\; \; -->(q)<0$.
Any help is appreciated!

Is this proposition true or false? What is the negation of the proposition?
I have the following proposition $x,y\in <!--\; \in \; -->\mathbb{R},\mathrm{\exists <!--\; \exists \; -->}x\mathrm{\exists <!--\; \exists \; -->}y(x^2+y^2<2xy)$. Is this proposition true or false? How can get its negation using Morgan's law?

Inductive Proof that $\sqrt{k+1}-<!--\; -\; -->\sqrt{k}\le <!--\; \le \; -->\frac{1}{\sqrt{k+1}}$
Help me understand this:
$\sqrt{k+1}-<!--\; -\; -->\sqrt{k}\le <!--\; \le \; -->\frac{1}{\sqrt{k+1}}$