Explore Discrete Math Examples

Discrete logarithm problem: does the base have to be a generator of Z?
${\mathbb{Z}}_p$ under multiplication, $p=13,Z=\{1,\dots 12\}$ I need to find the discrete logarithm of base 5 to 8:
So essentially $5^x\equiv <!--\; \equiv \; -->8(\mathrm{mod}13)$
However, In this problem 5 is not a generator of ${\mathbb{Z}}_{13\cdot <!--\; \cdot \; -->}$ 5 produces a cyclical group {5,12,8,1} which does not contain all the elements of ${\mathbb{Z}}_{13\cdot <!--\; \cdot \; -->}$
I understand there is a solution to this, but can someone clarify this rule for me?

In a party of n people, certain pairs of people shake hands with each other. In any group of k people, there exists at least one person who shakes hands with all other persons in that group. What is the minimum number of handshakes that can take place at the party?
The problem is inspired from a contest question which I want to solve in general. Here are my attempts in solving the problem:
There are $(\genfrac{}{}{0ex}{}{n}{k})$ possible groups. In each group, the minimum number of handshakes is $k-<!--\; -\; -->1$. So, at first I thought the answer should be $(k-<!--\; -\; -->1)(\genfrac{}{}{0ex}{}{n}{k})$. But I realized that the maximum number of handshakes is $(\genfrac{}{}{0ex}{}{n}{2})$. So, I was highly over counting.
Then, I tried for small cases. For $n=4$ and $k=3$, we have 4 people A,B,C,D. And there are 4 groups of 3. We take the first group (A,B,C) where A shakes hands with B and C. Then in the groups (A,B,D) and (A,C,D), B and D shake hands with D. So, we have a total of 4 handshakes as minimum in this case. From here, I think it's not easy to find the minimum for even small cases.
So, how to solve the problem?

Find a closed formula for the generating function given the recursion equation.
Suppose we have the recursion equation $b_{n+2}=5b_{n+1}-<!--\; -\; -->2b_n$. where $b_0=1,b_1=2$. I'm trying to find a closed formula for the generating function. I tried to find the characteristic equation and obtained $r^2-<!--\; -\; -->5r+2=0$. Then we could find $b_n=A{r}_1^n+B{r}_2^n$ by solving A and B from $b_0$ and $b_1$. The final result is
$$b_n=\frac{\sqrt{17}-<!--\; -\; -->1}{2\sqrt{17}}{\left(\frac{5+\sqrt{17}}{2}\right)}^n+\frac{\sqrt{17}+1}{2\sqrt{17}}{\left(\frac{5-<!--\; -\; -->\sqrt{17}}{2}\right)}^n$$
I wonder is there a different approach to solve for the generating function using recursive equation?

Discrete Math - non-negative intergers
Find the number of non-negative integer solutions to
$$x_1+x_2+x_3+x_4+x_5+x_6=3$$

Set Theory - I'm new at set theory and this problem I don't know how to start it please help
let's consider this two set A and B as:
$$A=\{\frac{(\mathrm{\Pi <!--\; \Pi \; -->})}{6}+\frac{k\mathrm{\Pi <!--\; \Pi \; -->}}{3}|k\in <!--\; \in \; -->Z\}$$
$$B=\{-<!--\; -\; -->\frac{(\mathrm{\Pi <!--\; \Pi \; -->})}{4}+\frac{k\mathrm{\Pi <!--\; \Pi \; -->}}{3}|k\in <!--\; \in \; -->Z\}$$
I started learning mathematics on my own, in my house, through the internet, I stadied logic, and now Set Theory, and I encountered some problems like , this set builder have this numbers, and this other set have this numbers, what is the result if you do intersection or union between them or something like this.
and this question I encountered it I answered the first one about how do you answer if I asked you is this two sets have in their intersection an emptyset like: $A\cap <!--\; \cap \; -->B=\mathrm{\varnothing <!--\; \varnothing \; -->}$ and after that I had this question below Question is:
How to determine the set:
$$(A\cup <!--\; \cup \; -->B)\cap <!--\; \cap \; -->[-<!--\; -\; -->\frac{\mathrm{\Pi <!--\; \Pi \; -->}}{2};\frac{\mathrm{\Pi <!--\; \Pi \; -->}}{2}]$$
in my first question I answered it using (A $\cap <!--\; \cap \; -->$ B is x in A and x in B ... and I said that means the first equation $\mathrm{\pi <!--\; \pi \; -->}/6+k\mathrm{\pi <!--\; \pi \; -->}/3=(-<!--\; -\; -->\mathrm{\pi <!--\; \pi \; -->}/4+k\mathrm{\pi <!--\; \pi \; -->}/3))$ and I solved that equation and I found that $k-<!--\; -\; -->k^{\prime }=a/b$ which is contradiction so the intersection is an empty set, now the second question is what I wrote above I still can't solve it.
here the only question that I need answer for is the one about this :
(
How to determine the set:
$$(A\cup <!--\; \cup \; -->B)\cap <!--\; \cap \; -->[-<!--\; -\; -->\frac{\mathrm{\Pi <!--\; \Pi \; -->}}{2};\frac{\mathrm{\Pi <!--\; \Pi \; -->}}{2}]$$
)<<< this is the one

Information about this type of recurrence relation
I've been noodling with a problem that requires me to find a set of recurrence relations and their solutions. In particular, all the recurrence relations are of the form:
$$u_{n+1}=u_n+p(n)$$
where p(x) is a polynomial.

Find a closed form for $\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{k}^5$ using generating functions.

Equivalence relation problem - discrete math
I'm having issues trying to start this question, what does defining a new relation mean?
The question:
Suppose $\mathrm{\rho <!--\; \rho \; -->}$ is reflexive and transitive relation on a set S. Define a new relation $\mathrm{\sigma <!--\; \sigma \; -->}$ as follows: $a\mathrm{\sigma <!--\; \sigma \; -->}b$ is true if and only if both $a\mathrm{\rho <!--\; \rho \; -->}b$ and $b\mathrm{\rho <!--\; \rho \; -->}a$ are true. Show that $\mathrm{\sigma <!--\; \sigma \; -->}$ is an equivalence relation.

Discrete math surjective function proof
Let E,F and G be given sets and let the functions $f:E\to <!--\; \to \; -->F$ and $g:F\to <!--\; \to \; -->G$ be given. Consider the claim:
if f is surjective and g is surjective $⟹<!--\; ⟹\; -->g\circ <!--\; \circ \; -->f$ is surjective.
The claim is either true or false. If it is true, prove it. If it is false, give example of 3 sets of E,F,G and two functions f,g where the fuctions $f:E\to <!--\; \to \; -->F$ and $g:F\to <!--\; \to \; -->G$ are surjective but $g\circ <!--\; \circ \; -->f$ isn't surjective.
How should I think about all of this? We've had so few tasks in our course on this subject

Calculate cardinality of a subset of all the relations above N
Define X to be set of all the relations R over N such that $R^{\ast <!--\; \ast \; -->}=\mathbb{N}\times <!--\; \times \; -->\mathbb{N}$, where R∗ is the transitive closure of R.
What is the cardinality of the set X?
What I've tried so far:
I notice that all the transitive relations besides $\mathbb{N}\times <!--\; \times \; -->\mathbb{N}$ are not in X. And I know that the cardinality of all the transitive relations over N is c.

Simplification of expression (related to multinomial theorem)
Is there a simplified way to write the following:
$$\underset{r_1+r_2+\cdots <!--\; \cdots \; -->+r_n=t,r_k\in <!--\; \in \; -->\mathbb{N}}{\sum <!--\; \sum \; -->}\frac{t!}{r_1!r_2!\cdots <!--\; \cdots \; -->r_n!}\underset{k=1}{\overset{n}{\prod <!--\; \prod \; -->}}f(k{)}^{r_k}$$
This is very similar to the multinomial theorem formula, however instead of $r_k$ being non-negative, $r_k$ is a natural number. In an expansion this is equivalent to just taking the values where every term is exponentiated to a power of one or greater, for example in the expansion of $(a+b+c{)}^4$ just taking $3(2a^{2}bc+2a{b}^{2}c+2ab{c}^2)$.

The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R.
$A=\{0,1,2,3,4\}$
$R=\{(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)\}$
Here is the solution:
$[0]=\{x\in <!--\; \in \; -->A|xR0\}=\{0,4\}$
$[1]=\{x\in <!--\; \in \; -->A|xR1\}=\{1,3\}$
$[2]=\{x\in <!--\; \in \; -->A|xR2\}=\{2\}$
$[3]=\{x\in <!--\; \in \; -->A|xR3\}=\{1,3\}$
$[4]=\{x\in <!--\; \in \; -->A|xR4\}=\{0,4\}$
Note that $[0]=[4]$ and $[1]=[3]$. Thus the distinct equivalence classes of the relation are {0,4}, {1,3}, and {2}.
My problem here is that I am not understanding the solution. I do not understand how it came up with an answer for each equivalence class of every element A. As in, how is {0,4} equal to $\{x\in <!--\; \in \; -->A|xR0\}$, and how is that equal to [0]? I can understand that $[0]=[4]$ since they both equal {0,4} but I'm not sure how to arrive at that answer.
I'm trying this problem:
$A=\{a,b,c,d\}$
$$R=\{(a,a),(b,b),(b,d),(c,c),(d,b),(d,d)\}$$
However, I am lost because I do not understand how to arrive at answers for every element in A.

Discrete maths
$$\begin{gathered} -<!--\; -\; -->3a_n+a_{n+1}=2^n \\ {a}_0=0 \end{gathered}$$

Discrete Math Proof: Divisibility equivalence
For all integers a, b, d, if d divides a, and d divides b, then d divides $(3a+2b)$ and d divides $(2a+b)$. Prove the statement.
What Assumptions do I need to make at the beginning of this proof that include $(3a+2b)$ and $(2a+b)$. I can start off the proof with:
Suppose a, b, d are integers and that d divides a, and d divides b. Then by definition of divisibility, there exist integers c, k, such that $a=dc$ and $b=dk$.

Derive a homogenous linear recurrence from $x_n=2^n+F_n$
Suppose that the sequence $x_n$ satisfies that
$$x_n=2^n+F_n$$
where $\{F_n\}$ denotes the Fibonacci sequence, I want to derive a homogenous linear recurrence for $x_n$
I can show that
$$x_n-<!--\; -\; -->x_{n-<!--\; -\; -->1}-<!--\; -\; -->x_{n-<!--\; -\; -->2}=\frac{1}{4}{2}^n$$
By plug in the relationship of Fib Sequence, however the above is non-homogenous, can anyone help?

I'm having trouble with the following:
$a_1=1$ and $a_n=1+\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{a}_i$ for $n>1$
How should I go about proving the below? Any hints?
$a_n=2^{n-<!--\; -\; -->1}$

Can the sum of two subsets without a maximal element have a maximal?
Let A, $B\subset <!--\; \subset \; -->R$ be two bounded subsets, neither of which has a maximal element. Can their “sum”, i.e. $A+B=\{a+bs.t.a\in <!--\; \in \; -->A,b\in B\}$ have a maximal element?

Show that all rational numbers Q fit into the Hilbert hotel
Can I prove this with help of simple induction grounded on the basic axioms of number theory and a linearity pattern?
$$\frac{-<!--\; -\; -->x}{y}\ne <!--\; \ne \; -->\frac{x}{y}$$
$$\frac{-<!--\; -\; -->x}{-<!--\; -\; -->y}=\frac{x}{y}$$
The complete set of rational numbers according to me.
$$P=\{\frac{a}{b},[-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}\le <!--\; \le \; -->(a,b)\le <!--\; \le \; -->\mathrm{\infty <!--\; \infty \; -->}],a,b\in <!--\; \in \; -->\mathbb{Z}\}$$
A subset of P is E.
E is a finite set with 50 unique elements. These elements fit in Hilbert's hotel.
$$E=\{\frac{a}{b},[-<!--\; -\; -->5\le <!--\; \le \; -->(a,b)\le <!--\; \le \; -->5],a,b\in <!--\; \in \; -->\mathbb{Z}\}$$
I derive the formula $r=10k$, where r is the amount of rooms needed.
$r=10k+10$, when $k+1$.
$$\{\frac{a}{b},[-<!--\; -\; -->k\le <!--\; \le \; -->(a,b)\le <!--\; \le \; -->k],a,b\in <!--\; \in \; -->\mathbb{Z}\}$$
when k goes to infinty r goes to infinity. I have successfully counted the amount of rooms needed for an infinite amount of fractions. This only shows it's possible to fit them in the hotel. But in order to show how, do I need a function to map all fractions systematically?

Discrete math on multipartite graph
1.The complete Multi-partite graph
$$K_{n_1,n_2,n_3,n_4,...,n_m}$$
2.the number of edge of
$$K_{n_1,n_2,n_3,n_4,...,n_m}$$

How can I prove that the following two statements are equivalent, using Formula Equivalence laws?
f(x) and (g(x) and h(x))
(f(x) and g(x)) and (f(x) and h(x))
I know that by associativity, f(x) and (g(x) and h(x)) is equal to (f(x) and g(x)) and h(x). I am also thinking to use distributive laws to prove this, but they state that $A\cup <!--\; \cup \; -->(B\cap <!--\; \cap \; -->C)=(A\cup <!--\; \cup \; -->B)\cap <!--\; \cap \; -->(A\cup <!--\; \cup \; -->C)orA\cap <!--\; \cap \; -->(B\cup <!--\; \cup \; -->C)=(A\cap <!--\; \cap \; -->B)\cup <!--\; \cup \; -->(A\cap <!--\; \cap \; -->C)$ (the law uses a union and intersection, rather than two intersections).
Any help to get me in the right direction would be greatly appreciated.