Explore Discrete Math Examples

Prove that $\underset{x\in <!--\; \in \; -->(1,\mathrm{\infty <!--\; \infty \; -->})}{\bigcup <!--\; \bigcup \; -->}[\frac{1}{x},x)=(0,\mathrm{\infty <!--\; \infty \; -->})$
Is my proof correct:
First I would define the union:
$S=\{y\in <!--\; \in \; -->\mathbb{R}\mid <!--\; \mid \; -->\mathrm{\exists <!--\; \exists \; -->}x\in <!--\; \in \; -->(1,\mathrm{\infty <!--\; \infty \; -->});y\in <!--\; \in \; -->[\frac{1}{x},x)\}$
1) $S\subset <!--\; \subset \; -->(0,\mathrm{\infty <!--\; \infty \; -->})$ proof: There exists x such that $[\frac{1}{x},x)\in <!--\; \in \; -->(0,\mathrm{\infty <!--\; \infty \; -->})$, let's say $x=2$
2) $(0,\mathrm{\infty <!--\; \infty \; -->})\subset <!--\; \subset \; -->S$ proof:
Let's say that $z\in <!--\; \in \; -->(0,\mathrm{\infty <!--\; \infty \; -->})$, we can pick $z=\frac{x}{2}⟹<!--\; ⟹\; -->\mathrm{\forall <!--\; \forall \; -->}z\in <!--\; \in \; -->[\frac{1}{x},x)⟹<!--\; ⟹\; -->\mathrm{\forall <!--\; \forall \; -->}z\in <!--\; \in \; -->S$
Is my proof correct ?

Showing that a relation is an equivalence relation
Let $\in <!--\; \in \; -->\mathbb{N}$ and ${\sim <!--\; \sim \; -->}_n\subseteq <!--\; \subseteq \; -->\mathbb{R}\times <!--\; \times \; -->\mathbb{R}$ be defined by: $x{\sim <!--\; \sim \; -->}_{n}y{\iff <!--\; \iff \; -->}_{df}{x}^n-<!--\; -\; -->y^n=nx-<!--\; -\; -->ny$. Show that ${\sim <!--\; \sim \; -->}_n$ is an equivalence relation.
And here is my take on it (I apologize in advance for any notation mistakes, I'm still not quite good at it.):
Proof Reflexivity: Let $x\in <!--\; \in \; -->\mathbb{R}$ and $n\in <!--\; \in \; -->\mathbb{N}$; to show: $x{\sim <!--\; \sim \; -->}_{n}x$
$\begin{array}{rl}x{\sim <!--\; \sim \; -->}_{n}x& {\iff <!--\; \iff \; -->}_{df}{x}^n-<!--\; -\; -->x^n=nx-<!--\; -\; -->nx\\ & \iff <!--\; \iff \; -->0=0\end{array}⟹<!--\; ⟹\; -->{\sim <!--\; \sim \; -->}_n$ is reflexive
Proof Symmetry: Let $x\in <!--\; \in \; -->\mathbb{R}$ and $n\in <!--\; \in \; -->\mathbb{N}$; to show: $x{\sim <!--\; \sim \; -->}_{n}y⟹<!--\; ⟹\; -->y{\sim <!--\; \sim \; -->}_{n}x$
$\begin{array}{rl}x{\sim <!--\; \sim \; -->}_{n}y& {\iff <!--\; \iff \; -->}_{df}{x}^n-<!--\; -\; -->y^n=nx-<!--\; -\; -->ny\\ y{\sim <!--\; \sim \; -->}_{n}x& \iff <!--\; \iff \; -->-<!--\; -\; -->(x^n-<!--\; -\; -->y^n)=-<!--\; -\; -->nx+ny\end{array}⟹<!--\; ⟹\; -->y\nsim <!--\; \nsim \; -->x$
So, the assumption made is wrong, that is, the relation is not symmetric, and therefore not an equivalence relation.
However, I'm unsure whether my proof is valid or not, as the wording of the question, and the following question, that requires ~ to be an equivalence relation, makes me believe it is in fact an equivalence relation.

Solving an inhomogenous linear recurrence with two approaches gives back inconsistent results.
In the textbook Mathematics for Computer Science (2004) by Lehman there is an example question in chapter 13.4.1 that tries to solve an inhomogenous recurrence:
$$\begin{gathered} f(1)=1 \\ f(n)=4f(n-<!--\; -\; -->1)+3^n \end{gathered}$$
By the textbook's method where you first solve the homogenous recurrence $f(n)=4f(n-<!--\; -\; -->1)$, and then find a particular solution for $f(n)=4f(n-<!--\; -\; -->1)+3^n$, and then guess the particular solutino to be of the form $d{3}^n$. Finally you solve for the constants, giving the answer of $f(n)=\frac{5}{2}{4}^n-<!--\; -\; -->3^{n+1}$. However by another method gives a different answer $f(n)=2\cdot <!--\; \cdot \; -->4^{n-<!--\; -\; -->1}-<!--\; -\; -->3^{n-<!--\; -\; -->1}$. The method is shown as follows:
$$\begin{gathered} a_n=4a_{n-<!--\; -\; -->1}+3^n \\ \frac{a_n}{3^n}+\frac{1}{3}=\frac{4}{3}(\frac{a_{n-<!--\; -\; -->1}}{3^{n-<!--\; -\; -->1}}+\frac{1}{3}) \end{gathered}$$
Solve f(n) as a regular geometric sequence and I had the above result. What's gone wrong with my approach? Or did I miss something in the transformation?

How many 4-permutations are there of the set $\{A,B,C,D,E,F\}$ if whenever A appears in the permutation, it is followed by E?
Case 1: when A does not appear in the 4-permutation
$5\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2=120$
Case 2: when A does appear in the 4-permutation. Then E should follow A. Let X stand for AE, now we should consider 3-permutations, since X occupies two spaces. Since X stands for two elements, we consider the number of elements to be 5.
$5\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->3=60$
Thus, number of permutations of the set $\{A,B,C,D,E,F\}$ where if whenever A appears in the permutation, it is followed by E is $120+60=180$.

Prove that the first list contains numbers from k to 2k and second list contains numbers from 1 to k.
There are two lists that contain integers from 1 to 2k such that the first list contains k randomly chosen integers from the range 1 - 2k and the second list contains the remaining numbers.
For Example: $A=8,6,13,14,4,11,12$ and $B=1,2,3,5,7,9,10$ when $k=7$.
Now arrange the first list such that it is in ascending order and the second list such that it is in descending order.Same Example: $A=4,6,8,11,12,13,14$ and $B=10,9,7,5,3,2,1$.
Now check the elements in the same position in both lists and make a swap such that the first list contains the greater number while the second list contains the smaller number.
Same Example: $A=10,9,8,11,12,13,14$ and $B=1,6,7,5,3,2,1$.
Prove that the first list contains numbers from k to 2k and second list contains numbers from 1 to k.
It will be really helpful if I can get some directions on how to do this question because a similar question of sort was asked but I don't think that the answer to that question was similar.
I have tried it several times and looked for any similar problem but couldn't find them. I know this might be very obvious but please help me out and If there is a similar problem with the solution I would be interested about reading up on it. Thanks.

The truth value of $(P):(\mathrm{\exists <!--\; \exists \; -->}m\in <!--\; \in \; -->\mathbb{Z})(\mathrm{\forall <!--\; \forall \; -->}y\in <!--\; \in \; -->\mathbb{Q}):my\in <!--\; \in \; -->\mathbb{N}$
Determine the truth value of the following statement:
$(P):(\mathrm{\exists <!--\; \exists \; -->}m\in <!--\; \in \; -->\mathbb{Z})(\mathrm{\forall <!--\; \forall \; -->}y\in <!--\; \in \; -->\mathbb{Q}):my\in <!--\; \in \; -->\mathbb{N}$
my attempt:
P is false, because suppose that exists $m\in <!--\; \in \; -->{\mathbb{Z}}_{-<!--\; -\; -->}^{\ast <!--\; \ast \; -->}$ such that:
$(\mathrm{\forall <!--\; \forall \; -->}y\in <!--\; \in \; -->\mathbb{Q}):my\in <!--\; \in \; -->\mathbb{N}$
let's take for example: $y=\frac{m}{m}\in <!--\; \in \; -->\mathbb{Q}$ we got:
$m.y=m.\frac{m}{m}=m\notin <!--\; \notin \; -->\mathbb{N}$ since $m\in <!--\; \in \; -->{\mathbb{Z}}_{-<!--\; -\; -->}^{\ast <!--\; \ast \; -->}$. Therefore, the statement (P) is false.

ISBN show that $x_{10}=\underset{i=1}{\overset{9}{\sum <!--\; \sum \; -->}}i{x}_i$
I want to show that for a ISBN-number $x_1{x}_2...x_{10}$ that satisfies $\underset{i=1}{\overset{10}{\sum <!--\; \sum \; -->}}i{x}_i\equiv <!--\; \equiv \; -->0\mathrm{mod}11$ the last digit must be $x_{10}=\underset{i=1}{\overset{9}{\sum <!--\; \sum \; -->}}i{x}_i\mathrm{mod}11$

What does $\bigwedge <!--\; \bigwedge \; -->\bigwedge <!--\; \bigwedge \; -->\bigvee <!--\; \bigvee \; -->$ mean in discrete mathematics?
- For each cell with a given value, we assert p(i, j, n) when the cell in row I and column j has the given value n.
- We assert that every row contains every number: ${\displaystyle \underset{i=1}{\overset{9}{\bigwedge <!--\; \bigwedge \; -->}}\underset{n=1}{\overset{9}{\bigwedge <!--\; \bigwedge \; -->}}\underset{j=1}{\overset{9}{\bigvee <!--\; \bigvee \; -->}}p(i,j,n)}$
I know that $\bigwedge <!--\; \bigwedge \; -->$ and $\bigvee <!--\; \bigvee \; -->$ bear the same relation to $\wedge <!--\; \wedge \; -->$ and $\vee <!--\; \vee \; -->$ respectively that $\sum <!--\; \sum \; -->$ does to +, i.e. ${\displaystyle \underset{i=1}{\overset{n}{\bigwedge <!--\; \bigwedge \; -->}}p(i)}$ can be interpreted as $p_1\wedge <!--\; \wedge \; -->p_2\wedge <!--\; \wedge \; -->p_3\wedge <!--\; \wedge \; -->p_4...\wedge <!--\; \wedge \; -->p_n$, but I don't know how to proceed when three symbols are together.

Suppose we are drawing some patches in a paper of size $1\times <!--\; \times \; -->1$. In the end, we discover that the sum of the area of all the patches is $>n$. Prove that there must exist at-least one point such that it lies in at-least $n+1$ of the patches.
This was a part in the proof of Blitchfeldt Theorem. The proof given in the link does not really seem convincing to me. The idea of contributions of points towards the area doesn't seem rigorous or at-least needs more justification in my opinion. So I was trying a "set-theoretic" approach, but could not get far.

Prove using classical logic that $q\to <!--\; \to \; -->r,r\to <!--\; \to \; -->p{⊢<!--\; ⊢\; -->}_c\mathrm{\neg <!--\; \neg \; -->}(\mathrm{\neg <!--\; \neg \; -->}p\wedge <!--\; \wedge \; -->q)$

Solving a problem using the Pigeonhole principle
How do I use the Pigeonhole principle to show that in a class of 25 students where every student is either a sophomore, freshman or a junior there are at least 9 sophomores or 9 seniors or 9 juniors ?
My solution: Assume by contradiction that there are 8 sophomores, 8 freshman and 8 juniors then $8+8+8=24\ne <!--\; \ne \; -->25$ thus by contradiction there are at least 9 sophomores or 9 seniors or 9 juniors
Is this solution a correct application of the Pigeonhole principle ?

Is there a Horn formula which is equivalent to $(p\vee <!--\; \vee \; -->q)$?
Is there a Horn formula which is equivalent to $(p\vee <!--\; \vee \; -->q)$?
Given any formula $\mathrm{\varphi <!--\; \varphi \; -->}$, is it possible to find a Horn formula equivalent to $\mathrm{\varphi <!--\; \varphi \; -->}$?
I know that a formula is Horn's if in its conjunctive normal form all clauses are Horn's.
But in this case $\mathrm{\varphi <!--\; \varphi \; -->}$ is already in it's conjunctive normal form, but $\mathrm{\varphi <!--\; \varphi \; -->}$ has 2 positive literal.
So, this would be a example that proves that what I have to answer is not possible, right?
Thanks in advance
UPDATE
I just thought of something; let me know if I'm right.
So a Horn Clause has the form:
a) $(p_1\wedge ...\wedge p_n)\to q$
b) $\mathrm{\neg <!--\; \neg \; -->}{p}_1\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}{p}_2,...,\mathrm{\neg <!--\; \neg \; -->}{p}_n$
Since $(p\vee <!--\; \vee \; -->q)$ is not equivalent to $(p\wedge <!--\; \wedge \; -->q)\to s$, and $(p\vee <!--\; \vee \; -->q)$ is not equivalent to $(\mathrm{\neg <!--\; \neg \; -->}p\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}q)$.
There $(p\vee <!--\; \vee \; -->q)$ can't be equivalent to any Horn formula.

Combinatorics question with unequality and different subscript
a) $x_1+x_2+...+x_7\le <!--\; \le \; -->30$ where $x_i^{\prime }s$ are even non-negative integers.
b) $x_1+x_2+...+x_7\le <!--\; \le \; -->30$ where $x_i^{\prime }s$ are odd non-negative integers.
c) $x_1+x_2+...+x_6\le <!--\; \le \; -->30$ where $x_i^{\prime }s$ are odd non-negative integers.
These questions is from my textbook. I know to solve similar questions such that $x_1+x_2+...+x_k\le <!--\; \le \; -->n$ where $x_i^{\prime }s$ are non-negative integers. We add an extra term on the lefthandside and the rest found by combination with repetition such that $(\genfrac{}{}{0ex}{}{n+(k+1)-<!--\; -\; -->1}{n})$. However , what happens when they are even or odd , is there any special technique ? Moreover , as you see the part a and b differ from only subscripts , i think that there must be a reason behind different subscript in same question.Is there any reason ? Thanks in advance..

How to use Fermat's Little theorem in ${12}^{{12}^{12}}\mathrm{mod}17$?

Suppose that a and b are real numbers with $0<a<1$ and $0<b<1$. Prove by contradiction or contrapositive: If $a^2+b^2=1$, then $a+b>1$.
So far I get the below:
To prove the above statement with contrapositive, we need to show that if $a+b\le <!--\; \le \; -->1$ then $a^2+b^2\ne <!--\; \ne \; -->1$. If $a+b\le <!--\; \le \; -->1$, then $a\le <!--\; \le \; -->1-<!--\; -\; -->b$. If we square both sides of the inequality we get $a^2\le <!--\; \le \; -->(1-<!--\; -\; -->b{)}^2$, which is $a^2\le <!--\; \le \; -->1-<!--\; -\; -->2b+b^2$, then $a^2-<!--\; -\; -->b^2\le <!--\; \le \; -->1-<!--\; -\; -->2b$.
I get to this step but I get $a^2-<!--\; -\; -->b^2$ instead of $a^2+b^2$, I don't know if I am on the right track or if it is possible to prove with contrapositive?

Condition making a relation reflexive
The relation $R=(a,b)\mid a=b\text{or}a=-b[a,b\in Z]$ is reflexive, as per Discrete Mathematics and Its Applications 8th Edition by Kenneth Rosen.
Is this because $a=b$ short-circuits the evaluation of $a=b$ or $a=-b$ (making it always true), or is there some other reason why the relation is reflexive?

Linear Diophantine equation with three variables and a condition
Let me start by saying that I'm new to Diophantine equations and my method certainly will not be the best possible one. I'm aware that a faster method of solving this particular case exists, but I want to know if what I did was correct and how I can finish the exercise.
$39x+55y+70z=3274$
$x+y+z=69$
$x\ge <!--\; \ge \; -->0,y\ge <!--\; \ge \; -->0,z\ge <!--\; \ge \; -->0$
What I tried:
$39x+55y=3274-<!--\; -\; -->70z$
The GCD for 39 and 55 is one, so we can set aside $z=t$ to be a parameter, where t is an integer. We proceed to solve this as a Diophantine equation with two variables.
I now need to use the extended Euclidean algorithm to express 1 as a linear combination of 39 and 55.
I got that $1=24\cdot <!--\; \cdot \; -->39-<!--\; -\; -->17\cdot <!--\; \cdot \; -->55$
Now, the solution would be
$x=78576-<!--\; -\; -->1680t+55s$
$y=-<!--\; -\; -->55658+1190t-<!--\; -\; -->39s$
$z=t$
where t and s are integers. I got this from the formula that $x={\mathrm{\lambda <!--\; \lambda \; -->}}_1\cdot <!--\; \cdot \; -->b+s\cdot <!--\; \cdot \; -->a_2$ and $y={\mathrm{\lambda <!--\; \lambda \; -->}}_2\cdot <!--\; \cdot \; -->b-<!--\; -\; -->s\cdot <!--\; \cdot \; -->a_1$.
Where ${\mathrm{\lambda <!--\; \lambda \; -->}}_1$ and ${\mathrm{\lambda <!--\; \lambda \; -->}}_2$ are the coefficients in the Euclidean algorithm, b is $3274-<!--\; -\; -->70t$ and $a_1$ and $a_2$ are 39 and 55, respectively.
It's obvious that $t\ge <!--\; \ge \; -->0$, and if I put that x and y are greater than zero, I get that
$s\ge <!--\; \ge \; -->\frac{1680t-<!--\; -\; -->78576}{55}$ and $s\le <!--\; \le \; -->\frac{-<!--\; -\; -->55658+1190t}{39}$ which makes $\frac{1680t-<!--\; -\; -->78576}{55}\le <!--\; \le \; -->\frac{-<!--\; -\; -->55658+1190t}{39}$ which is $t\le <!--\; \le \; -->46.77$.
I now have the whole range of integers [0,46] which of course isn't feasible to do (as I'd have to plug them into the inequalities for s and get even more cases.
How do I proceed from here? What do I do? I still have the condition $x+y+z=69$ but I feel like I'm missing something. Can it be really done this way, except that it's an unimaginably hefty job of testing each case?

How many different triples $f:A\to <!--\; \to \; -->S,g:B\to <!--\; \to \; -->S,h:C\to <!--\; \to \; -->S$ are there such that f, g, h are all injective, and $f(A)=g(B)=h(C)$?
In this Question we know that the $|A|,|B|,|C|=m>0$ and set S has cardinality $n>0.$.
Since the functions are one-to-one this means each domain maps a codomain and as all three sets (Domain) have same cardinality we can deduce that ${}_n{C}_m$ possible codomain mapped by these functions.
And because these functions are One-One, so each function can form ${}_n{P}_m$ number of One-One function so according to me this leads me to ${}_n{P}_m/{}_n{C}_m$ as number of different triples that can be formed.

Prove by Mathematical Induction ${𝑎}_{𝑛}<3𝑥,$, if ${𝑎}_1=3,𝑥\ge 2,$, and ${𝑎}_{𝑛+1}=\sqrt{2(2+{𝑎}_{𝑛})}$