Explore Discrete Math Examples

Discrete Math Help with a Proof
I need help to prove the following: Let a, b, and c be any integers. If a∣b, then a∣bc

Discrete math De Morgan's Laws. So like if I have a form $p^q$ and say I make p equal giving you cookies and q giving you milk so the sentence is just "Giving you cookies and giving you milk" like when I think about it if I think of the opposite(negation) I just automatically think it's not giving you cookies and not giving you milk but this is wrong but is it really? I mean am I just misunderstanding what opposite/negation means here?

Using Direct Proofs in Discrete Math
Use a direct proof to show that if x is a rational number, then $x^2$ is also a rational number.
I know I need to use the definition of rational numbers but don't know how to do it in this problem.

Validity of arguments in discrete math
All girls are tall.
Anyone who is tall and dark will pass.
Claire is a girl.
Conclusion: Claire will pass.
converting the statements to predicate logic:
- $G(x)=x$ is a girl
- $A(x)=x$ is tall
- $B(X)=x$ is dark
- $C(x)=x$ passes
$$\begin{gathered} \forall (x)[G(x)\to <!--\; \to \; -->A(x)] \\ \forall (x)[[A(x)\wedge <!--\; \wedge \; -->B(x)]\to <!--\; \to \; -->C(x)] \\ G(c)\to <!--\; \to \; -->A(c) \end{gathered}$$ .....................c stands for claire
Am i right till now? and please help me proceed to finish the problem .

Assuming D is the set of all dogs, H is the set of all homes, and BT(d,h) means that the dog d is in home h
Let's say I have a group of dogs and I want to say that every dog is in exactly one home. How would I represent that using predicate logic? So far I got, For all d in D, There exists a h in H, belongs to (d,H) AND....

A tight bound for $T(n)=2^{n}T(\frac{n}{2})+n^n$
Given recurrence
$$T(n)=2^{n}T\left(\frac{n}{2}\right)+n^n$$
How we can show that $T(n)\le <!--\; \le \; -->n^n$?
I show that $T(n)\ge <!--\; \ge \; -->n^n$ because of existence the term $n^n$ in T(n).

Chessboard by dominoes in Discrete Math
In how many ways can you cover a $2\times <!--\; \times \; -->n$ chessboard by dominoes?

Discrete math Group - Isomorphism and Automorphism
Let G be a Cyclic group
Prove or disprove: A.let $a,b\in <!--\; \in \; -->G$ so the function $f:G\to <!--\; \to \; -->G,f(a^k)=b^k$ is Automorphism of G(which means G is Isomorphism to herself)
B.let a,b generators of G so the function $f:G\to <!--\; \to \; -->G,f(a^k)=b^k$ is Automorphism of G(which means G is Isomorphism to herself)

Discrete math and recursion problem.
Let $b_1=3$
$b_n=n(n+2)$
From that question I wanted to do the $n+1th$ step as well for the recursion process and i got this:
$b_{n+1}=b_n+3$
however, that is wrong and apparently it is missing a $+2n$ in it:
$$b_{n+1}=b_n+2n+3$$
Can someone please explain how the book got 2n?

Prove or disprove $2^{an}=O(2^n)$
I was wondering if someone could verify or correct my work.
For all $a\ge <!--\; \ge \; -->1$ Prove or Disprove $2^{an}$ belongs to big-o of $2^n$
By definition, if there is a positive integer 'N' and a positive integer 'c' then $f(n)\ge <!--\; \ge \; -->g(n)$, for all $n>N$.
Therefore,
$$\begin{array}{rl}{2}^{an}& \le <!--\; \le \; -->c\times <!--\; \times \; -->2^n\\ \log <!--\; \; -->(2^{an})& \le <!--\; \le \; -->c\times <!--\; \times \; -->\log <!--\; \; -->(2^n)\\ an\times <!--\; \times \; -->\log <!--\; \; -->(2)& \le <!--\; \le \; -->cn\times <!--\; \times \; -->\log <!--\; \; -->(2)\\ an& \le <!--\; \le \; -->cn\end{array}$$
let
$$c=1$$
$$n=1$$
Therefore,
$$a<=1$$
therefore our given statement cannot be true since there exists some ${}^{\prime }{a}^{\prime }>{=}^{\prime }{c}^{\prime }$

Are these two statements equivalent?
Express the statement that no one has more than three grandmothers.
G(x, y) : x is the grandmother of y
$$\mathrm{\exists <!--\; \exists \; -->}y(({\mathrm{\exists <!--\; \exists \; -->}}_a{\mathrm{\exists <!--\; \exists \; -->}}_b{\mathrm{\exists <!--\; \exists \; -->}}_c{\mathrm{\exists <!--\; \exists \; -->}}_d,(G(a,y)\wedge <!--\; \wedge \; -->G(b,y)\wedge <!--\; \wedge \; -->G(c,y)\wedge <!--\; \wedge \; -->G(d,y)))\to <!--\; \to \; -->(a=b\vee <!--\; \vee \; -->a=b\vee <!--\; \vee \; -->a=c\vee <!--\; \vee \; -->a=d\vee <!--\; \vee \; -->b=c\vee <!--\; \vee \; -->b=d\vee <!--\; \vee \; -->c=d))$$
This is my solution. What I am trying to say is that if there exists a person y (anyone) who has four grandmothers then at least two of those grandmothers must be the same.
Is this correct?
The books solution is this:
$$\mathrm{\forall <!--\; \forall \; -->}y(\mathrm{\neg <!--\; \neg \; -->}{\mathrm{\exists <!--\; \exists \; -->}}_a{\mathrm{\exists <!--\; \exists \; -->}}_b{\mathrm{\exists <!--\; \exists \; -->}}_c{\mathrm{\exists <!--\; \exists \; -->}}_d,(a\ne <!--\; \ne \; -->b\vee <!--\; \vee \; -->a\ne <!--\; \ne \; -->b\vee <!--\; \vee \; -->a\ne <!--\; \ne \; -->c\vee <!--\; \vee \; -->a\ne <!--\; \ne \; -->d\vee <!--\; \vee \; -->b\ne <!--\; \ne \; -->c\vee <!--\; \vee \; -->b\ne <!--\; \ne \; -->d\vee <!--\; \vee \; -->c\ne <!--\; \ne \; -->d\wedge <!--\; \wedge \; -->(G(a,y)\wedge <!--\; \wedge \; -->G(b,y)\wedge <!--\; \wedge \; -->G(c,y)\wedge <!--\; \wedge \; -->G(d,y))$$
I am thinking this means: For all persons y, there does not exist four different people each of whom is the grandmother of y.
It seems as if mine is simple the negation of his statement, where
$$\mathrm{\neg <!--\; \neg \; -->}p\to <!--\; \to \; -->q=\mathrm{\neg <!--\; \neg \; -->}q\wedge <!--\; \wedge \; -->p$$

Is this coding exercise well thought?
I have to create a code C of 5 words with length $n=6$, with the alphabet ${\mathbb{F}}_2=\{0,1\}$ that corrects 1 mistake.
I am new to coding theory so I am having some troubles with this particular question...
If it corrects 1 mistakes, that means that $d>2\cdot <!--\; \cdot \; -->1$ (I believe this is a well-known result [I prove it at my courses]), where d is the minimal distance of the code C defined as $d=d(\mathcal{C})=min\{d(x,y)|x,y\in <!--\; \in \; -->\mathcal{C},x\ne <!--\; \ne \; -->y\}$, and that distance in the definition is the Hamming distance defined as $d(x,y)=\mathrm{\#<!--\; \#\; -->}\{i|1\le <!--\; \le \; -->i\le <!--\; \le \; -->n,x_i\ne <!--\; \ne \; -->y_i\}$, being $x=(x_1,x_2,...,x_n)$ and $y=(y_1,y_2,...,y_n)$ elements in ${\mathbb{F}}_q^n$ (where ${\mathbb{F}}_q$ is the alphabet of the code, and n denotes the length of the words).
So, in my particular case I want that the minimal distance of the code is greater than 2, i.e., I want that there are no two different words in the code that have Hamming distance equal or lesser than 2, i.e., no two words in the code that have more than 4 coordinates equal to each other (as If they have four equal to each other, there would be $6-<!--\; -\; -->4=2$ different to each other, so the Hamming distance would be 2, and if there are 5 equal to each other, the Hamming distance would be 1 which is not valid). So, I begin to construct the code, by taking the first word:
$$(1,1,1,1,1,1)\in <!--\; \in \; -->{\mathbb{F}}_2^6$$
Then, I could take another one like:
$$(1,1,1,0,0,0)\in <!--\; \in \; -->{\mathbb{F}}_2^6$$
which satisfies the previous conditions. So, taking this kind of words, and taking on account the conditions that must hold, I could keep going with this ''constructive algorithm'' until I have 5 words. For example:
$$(1,0,0,1,0,0)\in <!--\; \in \; -->{\mathbb{F}}_2^6$$
$$(0,1,0,1,1,0)\in <!--\; \in \; -->{\mathbb{F}}_2^6$$
$$(0,0,0,0,0,0)\in <!--\; \in \; -->{\mathbb{F}}_2^6$$
And this would conclude the exercise (by taking all this 5 words listed above). I am not sure if this is a great argument and I would really appreciate if someone could give me some feedback on it...

Discrete math induction proof (divisibilty)
How to show that ${10}^n-<!--\; -\; -->(-<!--\; -\; -->1{)}^n$ is always divisible by 11 through proof of induction?

I've googled already for an explanation and examples that show the difference between logical and tautological equivalences. I understand that a tautological equivalence is first a logical one, but not necessary vice versa. Besides that as far as I've seen they are the same. Are the truth tables the same? What could be a good example that shows the differences between both?
Examples of the questions I was given on this matter: 1)$(pVq)-<!--\; -\; -->>r$ is the tautological equivalence of $(p-<!--\; -\; -->>r)\wedge (q-<!--\; -\; -->>r)2)p-<!--\; -\; -->>(qVr)$ is the tautological equivalence of $q-<!--\; -\; -->>(pVr)$ I have to demonstrate which one, if any of those two are true statements.
On this basis I have to understand the difference between tautological and logical equivalences, why one and not the other, both or none.

Predicates and Quantifiers in discrete math
Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for everybody. (ii) Everybody is waiting for somebody.
May i know how to solve this kind of question?

A 'non-numerical\analytic' proof that $(\genfrac{}{}{0ex}{}{n}{k})$ > $(\genfrac{}{}{0ex}{}{n}{k-<!--\; -\; -->1})$ for large $n\in <!--\; \in \; -->\mathbb{N}$
The number of k-subsets of [n] is given by the formula $(\genfrac{}{}{0ex}{}{n}{k})$ or ${}^n{C}_k$. They famously occur in the expansion of $(1+x{)}^n$ and they are given by the formula
$$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{(n-<!--\; -\; -->k)!k!}$$
Using this formula, it is easy to prove the inequality that $(\genfrac{}{}{0ex}{}{n}{k})>(\genfrac{}{}{0ex}{}{n}{k-<!--\; -\; -->1})$ for large enough $n\in <!--\; \in \; -->\mathbb{N}$. What this inequality says is that the number of ways of choosing $k-<!--\; -\; -->1$-subsets is eventually smaller than the number of ways of choosing k-subsets of [n].
One more way of showing this is by observing that $(\genfrac{}{}{0ex}{}{n}{k})$ is a polynomial in n of degree k and then, we can see that it will outgrow $(\genfrac{}{}{0ex}{}{n}{k-<!--\; -\; -->1})$ which is a lower degree polynomial in n.
Is there a more natural way of seeing this inequality without the use of calculations with the use of something more combinatorial-like? Possibly by exhibiting an injection between the $k-<!--\; -\; -->1$-subsets and k-subsets? Or by another interpretation of the numbers where it is easier to get such an injection? Or something else altogether?
Remark: My supervisor mentioned almost immediately that there was a way to see this using Symmetric Chain Decomposition. But I do not have the luxury of spending that much time on this. I apologise. I would be thankful if you could provide a proof based on the same.
Tl;dr: What I am looking for is something more along the lines of bijections or a different interpretation of the binomial coefficients that makes the inequality easier to see. I hope the approach doesn't rely heavily on calculations and at the same time, explains why the the inequality reverses for small n.

The way to prove that $\sigma (a)=3^k$ has no solution?
$\mathrm{\sigma <!--\; \sigma \; -->}(n)$ = sum of divisors of n is a divisors function.
How to prove there are no such a and $k\ge <!--\; \ge \; -->2$ satisfy $\mathrm{\sigma <!--\; \sigma \; -->}(a)=3^k$.
This proplem can be simplify to the case when a is a power of prime ($a=p^{\mathrm{\alpha <!--\; \alpha \; -->}}$) because
if $a=p_0^{{\mathrm{\alpha <!--\; \alpha \; -->}}_0}{p}_1^{{\mathrm{\alpha <!--\; \alpha \; -->}}_1}...p_n^{{\mathrm{\alpha <!--\; \alpha \; -->}}_n}$, then
$$\mathrm{\sigma <!--\; \sigma \; -->}(a)=\mathrm{\sigma <!--\; \sigma \; -->}(p_0^{{\mathrm{\alpha <!--\; \alpha \; -->}}_0})\mathrm{\sigma <!--\; \sigma \; -->}(p_1^{{\mathrm{\alpha <!--\; \alpha \; -->}}_1})...\mathrm{\sigma <!--\; \sigma \; -->}(p_n^{{\mathrm{\alpha <!--\; \alpha \; -->}}_n})=\underset{i=0}{\overset{n}{\prod <!--\; \prod \; -->}}\frac{p_i^{{\mathrm{\alpha <!--\; \alpha \; -->}}_i+1}-<!--\; -\; -->1}{p_i-<!--\; -\; -->1}$$

Discrete Math Equivalence Relation
Let f be some function with domain S and range T. Define a relation R by xRy to mean $f(x)=f(y)$. Prove that R is an equivalence relation. If 4 is a member of S, what are the members of [4] (the set of all elements equivalent to 4 under under this equivalence relation)?
I'm not sure what exactly this question is asking...what does "relation R by xRy" mean?

"Let m, n, and r be non-negative integers. How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC appears, and no other letters are used?"

Construct an injective function from N to P(N) in a way that f(n) is not finite for any $n\in <!--\; \in \; -->\mathbb{N}$ and prove that it is injective.
Problem. Construct an injective function from N to P(N) in a way that f(n) is not finite for any $n\in <!--\; \in \; -->\mathbb{N}$ and prove that it is injective.
This is what I have attempted so far and I just need someone to check if what I have done is correct, or maybe guide me on what I have done wrong. This is my first time taking a proofs course and I am trying my best to learn and attempt the questions.
So first I decided that $f(n)=\{n,\mathrm{\infty <!--\; \infty \; -->}\}$.
And then to prove injectivity I picked two elements, x and y such that
$$\{x,\mathrm{\infty <!--\; \infty \; -->}\}=\{y,\mathrm{\infty <!--\; \infty \; -->}\}⟹<!--\; ⟹\; -->x=y$$
Hence, injectivity is proved.