Explore Discrete Math Examples

Prove that $f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdot \cdot \cdot +a_{1}x+a_0,x^n=O(f(x))$

Can substitution be used to solve a single equation that represent a partial order with two variables?
I am still trying to wrap my head around partial orders and my algebra is not the best... My question is pertains to the following example:
ex.) Let a relation R be defined on the set of real numbers as follows: $xRy\iff 2x+y=3$. Prove that this relation is antisymmetric.
Solution: aRb is $(2a+b=3)$, since bRa is $2b+a=3$.
$(2a+b)-(2b+a)=3-3$
$2a+b-2b-a=0$
$a-b=0$
$a=b$
My question is, why subtract the two equations? Do we subtract the two equations because a partial order is a way to quantify how objects in a set are different from each other?And is it possible to solve the same equation by substitution?
I solved: $2x+y=3$
$x=3-<!--\; -\; -->y/2$
and plugged x back into the equation and solved for y.
$2(3-<!--\; -\; -->y/2)+y=3$
$3-<!--\; -\; -->y+y=3$
$3+y=3+y$
$y=y$
I tested a few values to find that the equation $2x+y=3$ is true for any value y that is added to $2(3-<!--\; -\; -->y/2)$

Is this function surjective or injective?
I have the following function $f:\mathbb{Z}\times <!--\; \times \; -->\mathbb{N}\to <!--\; \to \; -->\mathbb{Q},f(m,n)=m/n$. Is this function injective or surjective? How can I prove it? I'm new to discrete maths so please bear with me.

Count the number of integer solutions to $x_1+x_2+x_3+x_4+x_5+x_6=25$ when, $x_1,x_2,x_3$ are odd and $x_4,x_5,x_6$ are even and $x_i$ is N.

Prove $A\cap <!--\; \cap \; -->(B\cup <!--\; \cup \; -->C)=(A\cap <!--\; \cap \; -->B)\cup <!--\; \cup \; -->(A\cap <!--\; \cap \; -->C)$ with algebra of sets

How to Find Characteristic Equations?
I try to find the characteristic equations of given recurrences. My textbook finds it magically without doing a calculation but I don't understand how to do that. I write 1 page of equations to find the characteristic equation. Is there an easier way to find it?
$T(n)=2T(\frac{n}{2})+n+\log <!--\; \; -->2n$
$(n=2^k)$
$CE=(x-2{)}^2(x-<!--\; -\; -->1{)}^2$
How to find the CE without any calculation (That's what my textbook does)? Is it possible?

Proof of symmetric difference with empty set (Basics of discrete mathematics).
I am a newbie in learning discrete mathematics. I know that $A\mathrm{\Delta <!--\; \Delta \; -->}\{\}=A$ and $A\mathrm{\Delta <!--\; \Delta \; -->}A=\{\},$, but i don't understend why, and how can i prove it.
I tried to use basic definition of symmetric difference and got this: $A\mathrm{\Delta <!--\; \Delta \; -->}\{\}=(A\setminus <!--\; \setminus \; -->\{\})\cup <!--\; \cup \; -->(\{\}\setminus <!--\; \setminus \; -->A).$.
I can't find any information about proving those two statements, and about $A\setminus <!--\; \setminus \; -->\{\}$ and $\{\}\setminus <!--\; \setminus \; -->A$.
Is it correct and how does it work if yes?

The number of cliques of size 4 where all the edges are of the same colour is at most $\frac{(\genfrac{}{}{0ex}{}{n}{4})}{3^5}.$.
Let $K_n$ be the complete graph on n vertices. Prove that for all integers $n\ge <!--\; \ge \; -->4$, we can assign each edge one of 3 colours such that the number of cliques of size 4 where all the edges are of the same colour is at most $\frac{(\genfrac{}{}{0ex}{}{n}{4})}{3^5}.$.
Can someone give some hints? I am not able to see the problem.
There are $(\genfrac{}{}{0ex}{}{n}{2})$ edges in $K_n$.

Let $A=\{1,2,...,n\}$, and R be a relation on A (so $R\subset <!--\; \subset \; -->A\times <!--\; \times \; -->A$)
i) What is the minimal possible number of elements in R?
I tried calculating this as just a normal cartesian product which would have $n^2$ within the set. So R would also need n2 number of elements to be a proper subset of $A\times <!--\; \times \; -->A$.
ii) What is the maximal possible number of elements in R?
I'm a bit more confused by this one, but I think it would have something to do with calculating it as $2^{n^2}$ i.e., if n was 3 then it would be $2^9$ or 512 as the maximum number of elements.

Show that if four distinct integers are chosen between 1 and 60 inclusive, some two of them must differ by at most 19
I am trying to understand this question. This is from the book Essential Discrete Mathematics for Computer Science and Question is from Chapter one "the pigeonhole principle" So clearly we have to prove using pigeonhole principle
But lets say I choose the numbers 1,2,3, and 60 these numbers are clearly within 1 and 60 inclusive but no two numbers differ by at most 19. So what am I missing here?

Slope if true or false and also provide a verson.
Every union of disconnected subset of a metric space is disconnected.

Let H be a set of non-positive Horn clauses. Show that H it is satisfying.
Let H be a set of non-positive Horn clauses. Show that H it is satisfying.
Is this true if there are positive clauses in H?
I'm finding hard to answer this questio, I have think about it for a long time, but can't find a good example/aproach
Can somebody help me? I'm just starting to see Horn clauses

Finding and drawing equivalence class with a binary set defined on RxR
In the question, it has been asked to find and draw the equivalence classes of the relation $\sim$ on $(\mathbb{R}\times <!--\; \times \; -->\mathbb{R})\setminus <!--\; \setminus \; -->\{(0,0)\}$ which is defined as
$(x_1,x_2)\sim <!--\; \backslash sim\; -->(y_1,y_2)\text{if}(y_1,y_2)=\mathrm{\alpha <!--\; \alpha \; -->}(x_1,x_2)\text{, for some }\mathrm{\alpha <!--\; \alpha \; -->}\ne <!--\; \ne \; -->0$
On solving, I have obtained the equivalence class as
$\begin{array}{rl}[(a,b)]& =\{(x,y)\in <!--\; \in \; -->\mathbb{R}:(x,y)\sim <!--\; \backslash sim\; -->(a,b)\}\\ & =\{(x,y)\in <!--\; \in \; -->\mathbb{R}:(x,y)=\mathrm{\alpha <!--\; \alpha \; -->}(a,b)\}\end{array}$
On solving this, I got $x=\mathrm{\alpha <!--\; \alpha \; -->}a$ and $y=\mathrm{\alpha <!--\; \alpha \; -->}b$ and $x-<!--\; -\; -->y=\mathrm{\alpha <!--\; \alpha \; -->}(a-<!--\; -\; -->b)$ which will correspond to the set of straight lines having slope 1 and y-intercept $-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}(a-<!--\; -\; -->b)$ excluding the straight line passing.
But in the solution of this question, the equivalence class is given as the set of all straight lines passing through the origin(which is excluded).
I have just begun discrete math, and I am not getting any idea of the solution.
It would be really helpful if someone could help me with this.

Finding number of nonnegative solutions for the equation $x_1+x_2+x_3+x_4+x_5=9$ when $x_1\ge <!--\; \ge \; -->1,x_5\le <!--\; \le \; -->5$

Solving Non-Homogenous Recurrence Relation
I was interested in Solution of this Non-Homogenous Recurrence Relation
$f(n)=f(n-<!--\; -\; -->1)+f(n-<!--\; -\; -->3)+1$
The Base conditions are: $f(0)=1$
$f(1)=2$
$f(2)=3$
$f(2)=3$
Kindly help me in solving this Recurrence Relation, by any known method.

Need help understanding the total number of different one-to-one functions
Theorem: If A and B are two sets with $|A|=m$ and $|B|=n$, where $m\le <!--\; \le \; -->n$, then number of different one-to-one functions is $\frac{n!}{(n-<!--\; -\; -->m)!}$.
Proof: First consider the special case where $m=n$, then the total number of possible one-to-one functions is n! - next, if $m<n$ then the total number of one-to-one functions is $n(n-<!--\; -\; -->1)(n-<!--\; -\; -->2)...(n-<!--\; -\; -->m+1)$, multiplying this by $\frac{(n-<!--\; -\; -->m)!}{(n-<!--\; -\; -->m)!}$ we see the answer can now be expressed as $n(n-<!--\; -\; -->1)(n-<!--\; -\; -->2)...(n-<!--\; -\; -->m+1)\frac{(n-<!--\; -\; -->m)!}{(n-<!--\; -\; -->m)!}=\frac{n!}{(n-<!--\; -\; -->m)!}$
Two questions:
1. Where did $(n-<!--\; -\; -->m+1)$ come from?
2. Why does multiplying $n(n-<!--\; -\; -->1)(n-<!--\; -\; -->2)...(n-<!--\; -\; -->m+1)$ by $\frac{(n-<!--\; -\; -->m)!}{(n-<!--\; -\; -->m)!}$ result in $\frac{n!}{(n-<!--\; -\; -->m)!}$?

How can I solve this $(\forall x)(\exists y)P(x,y)<-<!--\; -\; -->>(\exists y)(\forall x)P(x,y)$?

Prove combinatorially the recurrence $p_n(k)=p_n(k-n)+p_{n-1}(k-1)$ for all $0<n\le k$
Recall that $p_n(k)$ counts the number of partitions of k into exactly n positive parts (or, alternatively, into any number of parts the largest of which has size n).