Explore Discrete Math Examples

Proof of logical equivalence
I have been trying to get my head around this but currently online classes are horrible plus there is not many instructions but how do i get from $(P\wedge <!--\; \wedge \; -->Q)-<!--\; -\; -->>(P\vee <!--\; \vee \; -->Q)$?
Based on what I understood we use the logical conditional statement $P\to <!--\; \to \; -->Q=$
to get $\sim <!--\; \sim \; -->(P\vee <!--\; \vee \; -->Q)\vee <!--\; \vee \; -->(P\vee <!--\; \vee \; -->Q)$.
Then we use De Morgan's Law to get $(\sim <!--\; \sim \; -->P$ $\vee <!--\; \vee \; -->\sim <!--\; \sim \; -->Q)\vee <!--\; \vee \; -->(P\vee <!--\; \vee \; -->Q)$.
After we use the associate and communicative law we end up with $(\sim <!--\; \sim \; -->P$ $\vee <!--\; \vee \; -->\sim <!--\; \sim \; -->Q)\vee <!--\; \vee \; -->(P\vee <!--\; \vee \; -->Q)$ which is a logical equivalence to $(P\to <!--\; \to \; -->Q)$ because $P\to <!--\; \to \; -->Q=\sim <!--\; \sim \; -->P\vee <!--\; \vee \; -->Q$.

Find the generating function of the sequence $(a_0,a_1,a_2,\dots <!--\; \dots \; -->)$ where $a_n=n{2}^n$
Here is how I approached it: First, I wrote out the first few terms of the sequence, (0, 2, 8, 24, 64).
Then, using the definition of a generating function, set up this summation: $\underset{n=0}{\overset{}{\sum <!--\; \sum \; -->}}n{2}^n{x}^n=\underset{n=0}{\overset{}{\sum <!--\; \sum \; -->}}n(2x{)}^n$
However, I am stuck here. I am not sure if this is the right start, but it seems promising.

"If" versus "and" in statements
Let I(x) be the statement “x has an Internet connection”and C(x, y) be the statement “x and y have chatted over the Internet ”, where the universe of discourse for the variables x and y consists of all the students in your class. Use quantifiers to express each of these statements.
1. There is a student in your class who has chatted with everyone in your class over the Internet. Answer is: $\exists x\forall y[x\ne y\to C(x,y)]$
2. There are at least two students in your class who have not chatted with the same person in your class. Answer is: $\exists x\exists y[x\ne y\wedge \forall z\neg (C(x,z)\wedge C(y,z))]$
I am confused about whether I should use "if" or "and". In the first question, "if" is used. In the second question "and" is used. But I would use "and" in the first statement.

Show that number $2^{3n}+3^{4n}$ is not divisible by number 73
I used mathematical induction.
1. For a basis, let $n=1$: $2^3+3^4=89$ which is clearly not divisible by 73.
2. Let's suppose that $2^{3n}+3^{4n}=8^n+{81}^n$ is not divisible by 73.
3. Then for $n+1$ we have:
$2^{3(n+1)}+3^{4(n+1)}=8^{n+1}+{81}^{n+1}=8^n.8+{81}^n\ast <!--\; \ast \; -->81$
Because we supposed $8^n+{81}^n$ is not divisible by 73 and numbers 8 and 81 are clearly not divisible by 73, number $2^{3n}+3^{4n}$ is not divisible by 73. Is this correct or should I take different approach?

Transform the $a_n$ to 'secondary degree 'equation
$a_n=2a_{n-<!--\; -\; -->1}+5a_{n-<!--\; -\; -->2}$ and tranform into this $x^2-<!--\; -\; -->2x-<!--\; -\; -->5=0$.
1. How would it be this $a_{n+1}+a_n-<!--\; -\; -->2^n=0$? I can't understand I can't beleive it is $x^2+x-<!--\; -\; -->2=0$ because it has $2^n$.
2. or if it was like $2^{n-<!--\; -\; -->1}$ or $2^{n+1}$. What happen in this cases?

Consider the non-homogeneous linear recurrence relations $a_n=2a_{n-1}+2^n$ find all solutions.
I can show that $a_n^{(h)}$ characteristic equation $r-<!--\; -\; -->2=0\to <!--\; \to \; -->a_n^{(h)}=\mathrm{\alpha <!--\; \alpha \; -->}{2}^n$.
But I'm stuck on $a_n^{(p)}$ characteristic equation $A{2}^n=2A{2}^{n-<!--\; -\; -->1}+2^n$
Simplifies to $-<!--\; -\; -->A=2$
$A=2A+2$

A question in my book, chapter relations Let $f:M\to N$ and $xRy\leftrightarrow <!--\; \leftrightarrow \; -->f(x)=f(y)$ prove that this is an equivalence relation (the proof for it being an equivalence relation is pretty straight forward and easy thus already done), and for a $f:M\to N$ injective, I should write the partition on M Which is defined by R.
So it is the second part that I have problems with, how could I write this partition? What would the equivalence classes be?

How many secret codes can be made by assigning each letter of the alphabet a (unique) different letter?
The letter A can be assigned in 26 ways
The letter B can be assigned in 25 ways...
The letter Z can be assigned in 1 ways
So the answer is 26!
and in Euler constant form is $e^{61.26170}$
However, the answer in the text book is $\approx (26!{)}^2/e$

Recursive function guess
$y_{n+2}-<!--\; -\; -->3y_{n+1}+2y_n=5$
I am having trouble with getting the right guess because the right side of the function is a constant. How do I get the right guess? I need to find the general solution

How many strings of five decimal digits must be starting or ending with an odd number?
How many strings of five decimal digits must be starting or ending with an odd number?
Everywhere, I looked over the internet they used this method:
Thus, number of ways $=5\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10=50000$ ways.
Thus, number of ways $=10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->5=50000$ ways.
Therefore, the strings of five decimal digits that start with an odd number or end with an odd number $=50000+50000=100000$.

Double union notation
The Cantor set C is defined as
$C=[0,1]\setminus <!--\; \setminus \; -->\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\bigcup <!--\; \bigcup \; -->}}\underset{k=0}{\overset{3^n-<!--\; -\; -->1}{\bigcup <!--\; \bigcup \; -->}}(\frac{3k+1}{3^{n+1}},\frac{3k+2}{3^{n+1}})$
Does the double union of sets work like the double summation?
I start counting from $n=0$ and then all of the k's.
I.e.
For $n=\mathrm{0...0}$, k goes from 0 to 0
$\underset{n=0}{\overset{0}{\bigcup <!--\; \bigcup \; -->}}\underset{k=0}{\overset{0}{\bigcup <!--\; \bigcup \; -->}}=(\frac{1}{3},\frac{2}{3})$
For $n=1$, $k=\mathrm{0...2}$.
$$\begin{gathered} \underset{n=0}{\overset{1}{\bigcup <!--\; \bigcup \; -->}}\underset{k=0}{\overset{2}{\bigcup <!--\; \bigcup \; -->}}=(\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->0+1}{3^{1+1}},\frac{3\cdot <!--\; \cdot \; -->0+2}{3^{1+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->1+1}{3^{1+1}},\frac{3\cdot <!--\; \cdot \; -->1+2}{3^{1+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->2+1}{3^{1+1}},\frac{3\cdot <!--\; \cdot \; -->2+2}{3^{1+1}})=(\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{1}{9},\frac{2}{9})\cup <!--\; \cup \; -->(\frac{4}{9},\frac{5}{9})\cup <!--\; \cup \; -->(\frac{7}{9},\frac{8}{9})= \\ (\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{1}{9},\frac{2}{9})\cup <!--\; \cup \; -->(\frac{7}{9},\frac{8}{9}) \end{gathered}$$
For $n=2$, $k=\mathrm{0...8}$
$\underset{n=0}{\overset{2}{\bigcup <!--\; \bigcup \; -->}}\underset{k=0}{\overset{8}{\bigcup <!--\; \bigcup \; -->}}=(\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{1}{9},\frac{2}{9})\cup <!--\; \cup \; -->(\frac{7}{9},\frac{8}{9})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->0+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->0+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->1+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->1+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->2+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->2+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->3+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->3+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->4+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->4+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->5+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->5+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->6+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->6+2}{3^{2+1}})\cup <!--\; \cup \; -->(\frac{3\cdot <!--\; \cdot \; -->7+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->7+2}{3^{2+1}})(\frac{3\cdot <!--\; \cdot \; -->8+1}{3^{2+1}},\frac{3\cdot <!--\; \cdot \; -->8+2}{3^{2+1}})=$
$(\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{1}{9},\frac{2}{9})\cup <!--\; \cup \; -->(\frac{7}{9},\frac{8}{9})\cup <!--\; \cup \; -->(\frac{1}{27},\frac{2}{27})\cup <!--\; \cup \; -->(\frac{4}{27},\frac{5}{27})\cup <!--\; \cup \; -->(\frac{7}{27},\frac{8}{27})\cup <!--\; \cup \; -->(\frac{10}{27},\frac{11}{27})\cup <!--\; \cup \; -->(\frac{13}{27},\frac{14}{27})\cup <!--\; \cup \; -->(\frac{16}{27},\frac{17}{27})\cup <!--\; \cup \; -->(\frac{19}{27},\frac{20}{27})\cup <!--\; \cup \; -->(\frac{22}{27},\frac{23}{27})\cup <!--\; \cup \; -->(\frac{25}{27},\frac{26}{27})=$
$(\frac{1}{3},\frac{2}{3})\cup <!--\; \cup \; -->(\frac{1}{9},\frac{2}{9})\cup <!--\; \cup \; -->(\frac{7}{9},\frac{8}{9})\cup <!--\; \cup \; -->(\frac{1}{27},\frac{2}{27})\cup <!--\; \cup \; -->(\frac{7}{27},\frac{8}{27})\cup <!--\; \cup \; -->(\frac{19}{27},\frac{20}{27})\cup <!--\; \cup \; -->(\frac{25}{27},\frac{26}{27})$
For $n=3$, $k=\mathrm{0...26}$.

Determine whether f is a function from the set of all bit strings to the set of integers.
Qustion: Determine whether f is a function from the set of all bit strings to the set of integers if
(a) f(S) is the position of a 0 bit in S.
(b) f(S) is the number of 1 bits in S.
(c) f(S) is the smallest integer i such that the ith bit of S is 1 and $f(S)=$ 0 when S is the empty string, the string with no bits.
I did managed to solve this, but the similar solutions for all three questions make me quite unsure about my responses.
The following are my approaches:
(a) f(S) is either a surjective or onto function, as there always is an integer matching with the location of 0 in a bit string, and 0s may have same locations despite the overall bit string being different. Though, it's unsure whether all integers will having a matching value. It is still a function as it is a surjection.
(b) f(S) is either a surjective or onto function, as there always is an integer matching with the number of 1 bits in a bit string, and different bit strings may share the same number of 1 bits. Though, is unsure whether all integers will have a matching value. It is still a function as it is a surjection.
(c) f(S) is either a surjective or onto function, as there always is an integer matching with the "earliest" location of 1 bit in a string, and different bit strings may contain the "earliest" 1 bit on the same location. Though, it is unsure whether all integers will have a matching value. It is still a function as it is a surjection.
All questions seem to have similar responses with a slightly different supporting reason. Did I make a correct approach? What is the proper way of solution, and how should I correct my errors?

$\text{Dividend}=-<!--\; -\; -->11,\text{Divisor}=3,\text{Quotient}=-<!--\; -\; -->4,\text{Remainder}=1$ where A and B are sets.
The main problem was to either prove or disprove the statement.
I do not know how to approach the proof.
If I fix A, then if $\forall B((B=A)\vee (B⊈A))$ is false, any implication from it always true so we can ignore the cases when it is false. Because $P\to Q$ is always true when P is false.
Now, about the case when for a fix A, $\forall B((B=A)\vee (B⊈A))$ is true. What should it imply? Because when P is true and Q is false $P\to Q$ is false.
I am stuck here and I don't even know if this is the way to solve. Please show a proper approach.

Recurrence Relation (asymptotic notation)
The question is - Solve the recurrence: $T(n)=T(n/2)+O(n)$ and $T(1)=c$, where c is constant.

How wrong is the following in predicate logic
If P(x,y) means that x is perpendicular to y. And Q(x,y) means that x is parallel to y, how wrong is the following written in predicate logic:
Every x is perpendicular to y. In predicate: $\mathrm{\forall <!--\; \forall \; -->}x,\mathrm{\forall <!--\; \forall \; -->}y\in <!--\; \in \; -->P(x,y)$
There exists y that is parallel to x. In predicate: "For x there $\mathrm{\exists <!--\; \exists \; -->}y\in <!--\; \in \; -->Q(x,y)$
I know that the upper aren't totally correct. My question is how wrong are they?

Why do we say $11÷<!--\; ÷\; -->3$ is -4 with remainder 1, instead of -3 with remainder -2?
Specifically, since $-<!--\; -\; -->11=(-<!--\; -\; -->3)\times <!--\; \times \; -->3+(-<!--\; -\; -->2)$, why do we not say that the quotient is -3 and the remainder is -2?

Solve for $20x+15\equiv <!--\; \equiv \; -->47(\mathrm{mod}4),$, if there are no solution why?
I tried to do it the following way, but i'm wondering if it is the way it should be done. Is it correct?
$20x+15\equiv <!--\; \equiv \; -->47(\mathrm{mod}4),$, subtract 15 from 47, $20x\equiv <!--\; \equiv \; -->32(\mathrm{mod}4),$, divide both sides by 4, $5x\equiv <!--\; \equiv \; -->8(\mathrm{mod}4),$, $x\equiv <!--\; \equiv \; -->0.$

How is $a=-<!--\; -\; -->b$ symmetric?
$R3=(a,b)|a=b$ or $a=-<!--\; -\; -->b$ is a relation on set of integers
Which of the following pairs does R3 contains?
$(1,1),(1,2),(2,1),(1,-<!--\; -\; -->1),(2,2)$
I know that (1,1) , (2,2) and (1, -1) are in R3. The thing is: The book says it's a symmetric relation. I know that that for each pair (a,b), if it's symmetric, (b,a) must be in the relation, so (1,1) and (2,2) are fine. I'm just struggling to find out why (1, -1) does so, because I guess that (-1,1) and (1, -1) are different.
If someone could explain me this I'd be thankfull.

I need help with proving a summation with induction - mainly just help point me in the right direction please
For all integers $n\ge <!--\; \ge \; -->0,$,
$\underset{i=1}{\overset{n+1}{\sum <!--\; \sum \; -->}}i{2}^i=n{2}^{n+2}+2.$
I'm not sure how to start this and how to get it going, I thought I would start with the base case and make $n=1$, but it doesn't make both sides equal to each other and with the induction step I am just not fully sure how to get it going. Any help would be appreciated, thanks!

Representing anti-simmetric relations with directed graphs
Directed graph are used to represent relations.
I read somewhere that directed graph where arrows go only in one direction represent anti-simmetric relations. What justifies this kind of relation between directed graph and antisimmetric relations?