Explore Discrete Math Examples

Number of possible values for a sum of n variables
Let $x_k\in <!--\; \in \; -->\{2^k,-<!--\; -\; -->2^k\}$ where $k\in <!--\; \in \; -->\{0,1,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1\}$.
I am trying to check if the possible values for $y:=x_0+x_1+\dots <!--\; \dots \; -->+x_{n-<!--\; -\; -->1}$ are unique?
I was trying to prove that they are indeed unique by induction. If $y=x_0$, they are unique. By induction hypothesis, let the possible values for $y=x_0+x_1+\dots <!--\; \dots \; -->+x_k$ be unique but am not sure how to apply that for the sum of $k+1$ terms. Any ideas for proving or disproving this?

Existence of a path of length n/2 in every bipartite graph with $d(A,B)=1/2$
Claim: Let $G=A\cup <!--\; \cup \; -->B$ be a balanced bipartite graph with $e(A,B)\ge <!--\; \ge \; -->n/2$ then G has a path of length n/2.
I know about the erdos-gallai theorem that would net a path of length n/4. By noting that $d(G)=2E(G)/V(G)\ge <!--\; \ge \; -->n^2/4n$
I suspect that the condition of being bipartite forces the ecistence of a longer path, and I am yet unaware of such a result or a counterexample.
Part of my intuition is from the fact that considering a disjoint union of 2 copies of $K_{n/4-<!--\; -\; -->1,n/4}$ which are edge-maximal biparite graphs not containing such a path, we then have these two subgraphs and two yet to be connected vertices on A, also:
$2e(K_{n/4-<!--\; -\; -->1,n/4})=\frac{n^2}{8}-<!--\; -\; -->\frac{n}{2}<n^2/8$
And adding any edge would form a path of the desired length. Any help on how to go about proving this, or a reference for such a resukt would be greatly appreciated.

$G=(I_k|A)$ is a generator matrix of C iff $H=(-<!--\; -\; -->A^T|I_{n-<!--\; -\; -->k})$ is a control matrix of C
I am trying to prove that, ''given a C [n, k, d]-linear code, $G=(I_k|A)$ is a generator matrix of C iff $H=(-<!--\; -\; -->A^T|I_{n-<!--\; -\; -->k})$ is a control matrix of C''.
Firstly, I have supposed that $G=(I_k|A)$ is a generator matrix of C; we name the columns of A as $a_1,a_2,..,a_{n-<!--\; -\; -->k}$; if $x=(x_1,...,x_k)\in <!--\; \in \; -->{\mathbb{F}}_q^k$, I can codify this into a word of the code by taking the generator matrix and multiplying it this way: $xG=(x_1,...,x_k,x\cdot <!--\; \cdot \; -->a_1,...,x\cdot <!--\; \cdot \; -->a_{n-<!--\; -\; -->k})\in <!--\; \in \; -->\mathcal{C}$, where $\cdot <!--\; \cdot \; -->$ is the dot product of two vectors. I also know the following result:
H is a control matrix of C if the following holds: $x\in <!--\; \in \; -->\mathcal{C}$.
So, If I show $H(x_1,...,x_k,x\cdot <!--\; \cdot \; -->a_1,...,x\cdot <!--\; \cdot \; -->a_{n-<!--\; -\; -->k}{)}^T=(0,...,0{)}^T$, I would have show that $x\in <!--\; \in \; -->\mathcal{C}$; this is very easy to show taking on account how H is constructed.
For the other direction, I would have to show that $H{x}^T=(0,..,0{)}^T$ has, as a system of equations, as solutions all the words of the code... Here I get stucked.
Secondly, I would have to prove that, assuming $H=(-<!--\; -\; -->A^T|I_{n-<!--\; -\; -->k})$ is a control matrix of C, $G=(I_k|A)$ is a generator matrix of C. For this I suppose I would have to solve the system $H{x}^T=(0,...,0{)}^T$ (which, by hipothesis I know has as solutions the words of the code), and then show that each of that words can be generated by G, i.e., that, given a code word, I can find a vector in ${\mathbb{F}}_q^k$ such that the product of that vector by G is the code word firstly given. Nevertheless I am not sure this is the best approach...
Any help, guidance, or anything will be very helpful.

(Solved)Find the number of 9 letter words using the letters P, Q, and R containing at least one P and at least two Qs.
Please help me with the last question on my discrete maths assignment because I can't get what I am doing wrong.
Find the number of 9 letter words using the letters P, Q, and R containing at least one P and at least two Qs.
number of 9 letter words that use all 3 letters $=3^9$.
$A_1=$ number of 9 letter words without the use of P $=2^9$
$A_2=$ number of 9 letter words without the use of Q $=2^9$
$A_3=$ number of 9 letter words using at least 1 Q $=3^9-<!--\; -\; -->2^9$.
$A_1\cap <!--\; \cap \; -->A_2=1^9$
$A_1\cap <!--\; \cap \; -->A_3=2^9-<!--\; -\; -->1$
$A_2\cap <!--\; \cap \; -->A_3=0$
$A_1\cap <!--\; \cap \; -->A_2\cap <!--\; \cap \; -->A_3=0$
number of words using at least 1 P and at least 2 Qs
$=3^9-<!--\; -\; -->(2^9+2^9+(3^9-<!--\; -\; -->2^9)-<!--\; -\; -->(1+2^9-<!--\; -\; -->1-<!--\; -\; -->0)+0)=0$
I can't understand where I am making a mistake because everything seems to make sense.

How many pairs of intersecting intervals can be chosen from two finite sets of disjoint intervals?
Let $\mathcal{K}:=\{I\cap <!--\; \cap \; -->J\mid <!--\; \mid \; -->I\in <!--\; \in \; -->\mathcal{I},J\in <!--\; \in \; -->\mathcal{J}\}\setminus <!--\; \setminus \; -->\{\mathrm{\varnothing <!--\; \varnothing \; -->}\},$, where $\mathcal{I}$ is a finite set of disjoint real intervals, and so is $\mathcal{J}$.
Obviously $|\mathcal{K}|\le <!--\; \le \; -->|\mathcal{I}||\mathcal{J}|$. Are there any better bounds on the cardinality of $\mathcal{K}$?
Where in the literature can one find related theory and results?

Prove based on functions
Prove that for all $f,g\in <!--\; \in \; -->\mathbb{N}\to <!--\; \to \; -->\{0,1\}$ there exist $h\in <!--\; \in \; -->\mathbb{N}\to <!--\; \to \; -->\mathbb{N}$ bijection so:
$f=g\circ <!--\; \circ \; -->h\to <!--\; \to \; -->f=g$
My attempt was to assume that for all $f,g\in <!--\; \in \; -->\mathbb{N}\to <!--\; \to \; -->\{0,1\}$ there exist $h\in <!--\; \in \; -->\mathbb{N}\to <!--\; \to \; -->\mathbb{N}$ bijection so: $f=g\circ <!--\; \circ \; -->h\wedge <!--\; \wedge \; -->f\ne <!--\; \ne \; -->g$ and try to get a contradiction without any succed.

Prove that if $A\subseteq <!--\; \subseteq \; -->B$, and A is uncountable, then B is uncountable"
I think that for an answer we could reason with cardinality as follows Suppose that B is countable, then $\mid <!--\; \mid \; -->B\mid <!--\; \mid \; -->\le <!--\; \le \; -->\mid <!--\; \mid \; -->\mathbb{N}\mid <!--\; \mid \; -->$.
But if $A\subseteq <!--\; \subseteq \; -->B$, then $|A|\le <!--\; \le \; -->|B|\le <!--\; \le \; -->|\mathbb{N}\mid <!--\; \mid \; -->$ that is untrue if A is uncountable, since any uncountable set should have higher cardinality then natural numbers.

P poset. $x=\bigvee <!--\; \bigvee \; -->(\downarrow <!--\; \downarrow \; -->x\cap <!--\; \cap \; -->U)\Rightarrow <!--\; \Rightarrow \; -->\mathrm{\forall <!--\; \forall \; -->}x,y\in <!--\; \in \; -->P$ with $y<<!--\; <\; -->x$, $\mathrm{\exists <!--\; \exists \; -->}a\in <!--\; \in \; -->U$ s.t. $a\le <!--\; \le \; -->x$ and $a⪇<!--\; ⪇\; -->y$.

How to prove this inequality with the simplest means?
$x^2+5y^2+6z^2\ge <!--\; \ge \; -->4\sqrt{5xy{z}^2},\text{ if }xy>0$
I was trying to prove it. The right hand side should be nonnegative, so I can square it on both sides. But once I have done it I get to a point, where I do not see how to show, that the statement is greater or equal to 0.
$x^4+25y^4+36z^4+10x^2{y}^2+12x^2{z}^2+60y^2{z}^2-<!--\; -\; -->80xy{z}^2\ge <!--\; \ge \; -->0.$.

Equivalence Relation on $\mathbb{N}\setminus <!--\; \setminus \; -->\{1\}$
$A_1=\{(x,y):x\text{ and }y\text{ are relatively prime}\}.$
Determine which one of the three properties are satisfied:
1) $(2,2)\notin <!--\; \notin \; -->A_1$. So it is not reflexive.
2) $(2,3)\to <!--\; \to \; -->(3,2)\in <!--\; \in \; -->A_1$. Is symmetric.
3) (2,3) and $(3,4)$. Is not transitive.
That means, $A_1$ is not an equivalence relation. Is it okay? Thanks in advance!

How to show $f:{\mathbb{Z}}^{+}\to <!--\; \backslash rightarrow\; -->{\mathbb{Z}}^{+},f(n)=n!$ is one-to-one?
How to show $f:{\mathbb{Z}}^{+}\to <!--\; \backslash rightarrow\; -->{\mathbb{Z}}^{+},$, $f(n)=n!$ is one-to-one?
I'm quite sure the function is one-to-one as 0 is not an element of the domain, so $f(0)=f(1)$ is not a concern. However doing something like setting $f(m)=f(v)$ where m,v are arbitrary elements of the domain doesn't really work, since n! doesn't have an inverse.
I was able to get something working algebraically by also doing $f(m+1)=f(v+1)$, but I'm quite sure it is circular to do something like that.
Any nudge in the right direction would be greatly appreciated.

One cinema has 3 rooms (A,B,C). Room A needs 6 workers inside, B needs 5 workers and C needs 9 workers. How many ways can the owner of the cinema choose 3 teams of workers given that he has 50 workers available?

Upperbound for difference between chromatic number $\mathrm{\chi <!--\; \chi \; -->}(G)$ and list-chromatic number ${\mathrm{\chi <!--\; \chi \; -->}}_L(G)$

Prove that successive differences between square roots of integers decreases without using limits or derivatives
I have been trying to prove that $\sqrt{n+1}-<!--\; -\; -->\sqrt{n}>\sqrt{n+2}-<!--\; -\; -->\sqrt{n+1}$ for ALL $n=1,2,3,...$ without success.

From homogeneous to non-homogeneous linear recurrence relation
I'm trying to do the following exercise:
Find a non-homogeneous recurrence relation for the sequence whose general term is
$a_n=\frac{1}{2}{3}^n-<!--\; -\; -->\frac{2}{5}{7}^n$
From this expression we can obtain the roots of the characteristic polynomial P(x), which are 3 and 7, so $P(x)=x^2-<!--\; -\; -->10x+21$ and $a_n=10a_{n-<!--\; -\; -->1}-<!--\; -\; -->21a_{n-<!--\; -\; -->2}\mathrm{\forall <!--\; \forall \; -->}n\ge <!--\; \ge \; -->2,a_0=\frac{1}{10},a_1=-<!--\; -\; -->\frac{13}{10}$
Now I don't know how to obtain a non-homogeneous recurrence relation given this homogeneous recurrence relation.

Recurrence relation and closed formula
I have the following problem:
I must find the closed formula for
$a_n=b_n+{\mathrm{\lambda <!--\; \lambda \; -->}}_1{a}_{n-<!--\; -\; -->1}+{\mathrm{\lambda <!--\; \lambda \; -->}}_2{a}_{n-<!--\; -\; -->2}$
where $b_n=\frac{\mathrm{\Gamma <!--\; \Gamma \; -->}(n+d)}{\mathrm{\Gamma <!--\; \Gamma \; -->}(d)\mathrm{\Gamma <!--\; \Gamma \; -->}(n+1)},d\in <!--\; \in \; -->\mathbb{R}.$.
I don't have any experience in recurrence relations or discrete math, I'm trying to find some book recommendations to study this. I know that recurrences like
$a_n={\mathrm{\lambda <!--\; \lambda \; -->}}_1{a}_{n-<!--\; -\; -->1}+{\mathrm{\lambda <!--\; \lambda \; -->}}_2{a}_{n-<!--\; -\; -->2}$
have closed formulas, but I'm stuck with the $b_n$ term.
In a more general way, I'm searching a closed formula for a relation like
$a_n=b_n+\underset{i=1}{\overset{p}{\sum <!--\; \sum \; -->}}{\mathrm{\lambda <!--\; \lambda \; -->}}_i{a}_{n-<!--\; -\; -->i}.$
If any condition is not clear, please tell me so I can adjust it. Thanks!

How many strictly increasing functions $[4]\to <!--\; \to \; -->[12]$ precede (2,3,4,5)?
I'm having some trouble with the following question:
Notation: Let [n] denote the set $\{1,...,n\}$ and we will represent a function $[k]\to <!--\; \to \; -->[n]$ as a list: $(f(1),f(2),...,f(k))$
Consider all strictly increasing functions $[4]\to <!--\; \to \; -->[14]$ and order them with the natural lexicographic order induced by the order in [14]. How many functions precede the function (2,3,4,5)?
- $(\genfrac{}{}{0ex}{}{13}{4})$
$(\genfrac{}{}{0ex}{}{13}{3})$
$(\genfrac{}{}{0ex}{}{15}{3})$
$(\genfrac{}{}{0ex}{}{14}{3})$

Discrete Mathematics Division Algorithm proof
I'm not quite sure how to do this problem if anyone can do a step by step to help me understand it I would appreciate it a lot.
Let a and b be positive integers with $b>a$, and suppose that the division algorithm yields $b=a\cdot <!--\; \cdot \; -->q+r$, with $0\le <!--\; \le \; -->r<a$. (note: its a zero)
Prove that $\mathrm{l}\mathrm{c}\mathrm{m}(a,b)-\mathrm{l}\mathrm{c}\mathrm{m}(a,r)=\frac{a^2\cdot <!--\; \cdot \; -->q}{gcd(a,b)}.$