Explore Discrete Math Examples

Proving $\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{1}{lcm(a_i,a_{i+1})}<<!--\; <\; -->1$ for a set of increasing positive integers.
Assume $a_1,a_2,...,a_n$ are numbers $\in <!--\; \in \; -->\mathbb{N}$ such that $a_1<<!--\; <\; -->a_2<<!--\; <\; -->...<<!--\; <\; -->a_n$ prove: $\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{1}{lcm(a_i,a_{i+1})}<<!--\; <\; -->1$

Untyped λ-calculus: proof that for any binary relation $R\models <!--\; \models \; -->\mathrm{◊<!--\; ◊\; -->}\Rightarrow <!--\; \Rightarrow \; -->R^{\ast <!--\; \ast \; -->}\models <!--\; \models \; -->\mathrm{◊<!--\; ◊\; -->}$
I'm currently in the process of reading Barendregt's "The Lambda Calculus - Its Syntax and Semantics" (1985 revised edition) and I've stumbled across a lemma whose proof I can't quite comprehend. The lemma (3.2.2) states that for all binary relations R on a set the following holds:
$R\models <!--\; \models \; -->\mathrm{◊<!--\; ◊\; -->}\Rightarrow <!--\; \Rightarrow \; -->R^{\ast <!--\; \ast \; -->}\models <!--\; \models \; -->\mathrm{◊<!--\; ◊\; -->}$, where $\mathrm{◊<!--\; ◊\; -->}$ is the diamond property of a relation:
$R\models <!--\; \models \; -->\mathrm{◊<!--\; ◊\; -->}⟺<!--\; ⟺\; -->\mathrm{\forall <!--\; \forall \; -->}M,M_1,M_2[(M,M_1)\in <!--\; \in \; -->R\wedge <!--\; \wedge \; -->(M,M_2)\in <!--\; \in \; -->R\Rightarrow <!--\; \Rightarrow \; -->\mathrm{\exists <!--\; \exists \; -->}{M}_3[(M_1,M_3)\in <!--\; \in \; -->R\wedge <!--\; \wedge \; -->(M_2,M_3)\in <!--\; \in \; -->R]]$, and R∗ is the transitive closure of R:
$\mathrm{\forall <!--\; \forall \; -->}M,N[(M,N)\in <!--\; \in \; -->R\Rightarrow <!--\; \Rightarrow \; -->(M,N)\in <!--\; \in \; -->R^{\ast <!--\; \ast \; -->}]$ and $\mathrm{\forall <!--\; \forall \; -->}M,N,L[(M,N)\in <!--\; \in \; -->R^{\ast <!--\; \ast \; -->}\wedge <!--\; \wedge \; -->(N,L)\in <!--\; \in \; -->R^{\ast <!--\; \ast \; -->}\Rightarrow <!--\; \Rightarrow \; -->(M,L)\in <!--\; \in \; -->R^{\ast <!--\; \ast \; -->})].$.

How many ternary strings with at most k ones and k minus ones
Consider for $n,k\in <!--\; \in \; -->\mathbb{N}$ with $k\le <!--\; \le \; -->n$ the following set
$S_{k,n}:=\{z\in <!--\; \in \; -->\{-<!--\; -\; -->1,0,1{\}}^n:\mathrm{\#<!--\; \#\; -->}\{i:z_i=1\}\le <!--\; \le \; -->k\text{and}\mathrm{\#<!--\; \#\; -->}\{i:z_i=-<!--\; -\; -->1\}\le <!--\; \le \; -->k\}.$
I want to determine the cardinality of S. I know that there are $(\genfrac{}{}{0ex}{}{n}{k})2^{n-<!--\; -\; -->k}$ number of strings with exactly k ones and likewise $(\genfrac{}{}{0ex}{}{n}{k})2^{n-<!--\; -\; -->k}$ number of strings with exactly k ones and likewise $(\genfrac{}{}{0ex}{}{n}{k})2^{n-<!--\; -\; -->k}$ number of strings with exactly k minus ones. But I have to remove the strings where we have for example k one's and more than k minus ones. I think I have to use the Principle of Inclusion and Exclusion. I'm REALLY stuck on this problem. Hope someone can help me.
Example: let $n=3$ and $k=1$. Then we have
$S_{3,1}=\{(0,0,0),(1,-<!--\; -\; -->1,0),(1,0,-<!--\; -\; -->1),(0,1,-<!--\; -\; -->1),(-<!--\; -\; -->1,1,0),(-<!--\; -\; -->1,0,1),(0,-<!--\; -\; -->1,1),(0,0,1),(0,1,0),(1,0,0),(0,0,-<!--\; -\; -->1),(0,-<!--\; -\; -->1,0),(-<!--\; -\; -->1,0,0)\}$
and so we have $\mathrm{\#<!--\; \#\; -->}{S}_{3,1}=13$.

In how many ways can 30 identical balls be distributed into 6 distinct boxes (numbered box 1, ... , box 6) where each box gets an odd number of balls?

Normal disjunctive and conjuctive form from a truth table
Let's say that we get a table with zeros and ones. We need to get it into disjunctive normal form or conjuctive normal form. We also have discrete variables $x_1,..,x_n$ that are either 1 or 0. How do you determine where to put negation and where not to put it.
for instance: we have a row:
$p=0,q=1,r=0,\text{table row result = 1}$
Should I write this as: $...\vee <!--\; \vee \; -->(\mathrm{\neg <!--\; \neg \; -->}p\wedge <!--\; \wedge \; -->q\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}r)\vee <!--\; \vee \; -->...$
or $...\wedge <!--\; \wedge \; -->(\mathrm{\neg <!--\; \neg \; -->}p\vee <!--\; \vee \; -->q\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}r)\wedge <!--\; \wedge \; -->...$
What is the correct way ? What if the table row result would be zero?
Or the other way with negations? So my question is how do we know where the negations are?

How to find the probability and generating function for this problem?
We toss a coin k times which is having probability p of landing on heads and a probability $q=1-p$ of landing on tails. The probability of getting exactly n heads is denoted by $a_n$. What is $a_n$ and the generating function of the sequence $(a_n)$?

A Combinatorial Problem from HMMT-2009
Given a rearrangement of the numbers from 1 to n, each pair of consecutive elements a and b of the sequence can be either increasing or decreasing. How many rearrangements have of the numbers from 1 to n have exactly two increasing pairs?

A particular solution for the diffirencial equation: $(x+i)y^{\prime }+y=2x\arctan <!--\; \; -->x$
the original equation was: $(x+i)y^{\prime }+y=1+2x\arctan <!--\; \; -->(x)$
I solved for $(x+i)y^{\prime }+y=0$
then $(x+i)y^{\prime }+y=1$ now I'm working on the second term ($2x\arctan <!--\; \; -->(x)$)

Complement of a Set: What do I do when a set contains an element that is not in the Universal Set
Let $U=\{x:x\in <!--\; \in \; -->\mathbb{N},x>10andx<40\},A=5,10,20,40$.
The complement of the set should be
$A^c=\{\text{All natural numbers between greater than 10 and less than 40 except for 20}\}$ right?

For all integers m,n, prove $max(m,n)+min(m,n)=m+n$

Counting routes from home to office if you only return home if you realize you have forgotten something before you reach the office
The following is how you can go to the office from home:
Home $\to <!--\; \to \; -->$ Four Roads $\to <!--\; \to \; -->$ Schools $\to <!--\; \to \; -->$ Three Roads $\to <!--\; \to \; -->$ University $\to <!--\; \to \; -->$ Five Roads $\to <!--\; \to \; -->$ Parks $\to <!--\; \to \; -->$ Two Roads $\to <!--\; \to \; -->$ Offices
You are forgetful minded. You may have forgotten something at home. You remember what you forgot at home, either at your school or university or in the park, and you go back to pick it up. Then the journey continues from the beginning again. You forget one thing at most during the day and when you reach the office you do not go back to take back what you have left. So how many different routes are possible for you?
I have tried this way:
Case 1: I remember what I forgot at school:
In this case, I can go to school in 4 ways and come back in 4 ways and go back in 4 ways. Then I can start the journey from there in $3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->2$ ways.
Case 2: I remember what I forgot at university:
In this case, I can go to university in $4\cdot <!--\; \cdot \; -->3$ ways and come back in $4\cdot <!--\; \cdot \; -->3$ ways and go back in $4\cdot <!--\; \cdot \; -->3$ ways. Then I can start the journey from there in $5\cdot <!--\; \cdot \; -->2$ ways.
Case 3: I remember what I forgot at park:
In this case, I can go to park in $4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5$ ways and come back in $4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5$ ways and go back in $4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5$ ways. Then I can start the journey from there in 2 ways.
Case 4: I go to office without remembering:
In this case, I can go to the office in $4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->2$ ways.
So, total ways would be $=(4\cdot <!--\; \cdot \; -->3+3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->2)+(4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->3+5\cdot <!--\; \cdot \; -->2)+(4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->3)+2+4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->3$ ways.

To find the number of ways to put 14 identical balls into 4 bins with the condition that no bin can hold more than 7 balls.
I have tried the following:
The total no of ways to distribute 14 identical balls into 4 bins without any restriction is
$(\genfrac{}{}{0ex}{}{14+4-<!--\; -\; -->1}{4-<!--\; -\; -->1})=(\genfrac{}{}{0ex}{}{17}{3}).$.
Note that there can't be two bins with more than 7 balls since we have only 14 identical balls only.
Now, we count the no. of ways so that one bin has more than 7 balls. So, it has at least 8 balls and the remaining 6 can be distributed in $(\genfrac{}{}{0ex}{}{6+4-<!--\; -\; -->1}{4-<!--\; -\; -->1})=(\genfrac{}{}{0ex}{}{9}{3})$ ways. We can choose one bin out of 4 in 4 ways.
Hence the reqd number of ways = $(\genfrac{}{}{0ex}{}{17}{3})-<!--\; -\; -->4\times <!--\; \times \; -->(\genfrac{}{}{0ex}{}{9}{3}).$

How to solve the recurrence relation $a_n=\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{a}_i{a}_{n-<!--\; -\; -->i}$
The relation is: $$\begin{gathered} a_n=\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{a}_i{a}_{n-<!--\; -\; -->i} \\ n>1,a_1=2 \end{gathered}$$
I know I probably should create a generating function for $a_n$, like $G(x)=f(x)\ast <!--\; \ast \; -->g(x)$, but I'm not sure what f(x) and g(x) exactly should be, are they just $\sum <!--\; \sum \; -->a_i{x}^i$ and $\sum <!--\; \sum \; -->a_{n-<!--\; -\; -->i}{x}^{n-<!--\; -\; -->i}$? And are there any other methods to solve it? Any hint would be useful to me.

When proving divisibility by induction, how does $f(k+1)-<!--\; -\; -->f(k)$ help us to prove it?

Prove that $\forall x\forall y(P(x,y)\to \neg P(y,x)),\forall x\exists yP(x,y)$ be deduced to $\neg \exists v\forall zP(z,v)$.

Induction and Union of Sets
I'm trying to prove the following:
"Suppose that one has proven the proposition that if $A\subseteq <!--\; \subseteq \; -->B$ and $C\subseteq <!--\; \subseteq \; -->D$, then $A\cup <!--\; \cup \; -->C\subseteq <!--\; \subseteq \; -->B\subseteq <!--\; \subseteq \; -->D$. Prove that for any integer $n\ge <!--\; \ge \; -->2$ that if sets $A_1,A_2,...,A_n$ and $B_1,B_2,...B_n$ are sets that satisfy $A_j\subseteq <!--\; \subseteq \; -->B_j$ for $j=1,2,...,n$ then
$\underset{j=1}{\overset{n}{\bigcup <!--\; \bigcup \; -->}}{A}_j\subseteq <!--\; \subseteq \; -->\underset{j=1}{\overset{n}{\bigcup <!--\; \bigcup \; -->}}{B}_j."$
I'm not sure if I what I came up with makes sense logically, and would appreciate some feedback.
Proof:
Define P(n): $\underset{j=1}{\overset{n}{\bigcup <!--\; \bigcup \; -->}}{A}_j\subseteq <!--\; \subseteq \; -->\underset{j=1}{\overset{n}{\bigcup <!--\; \bigcup \; -->}}{B}_j$.
Base case $(n=2)$:
$\underset{j=1}{\overset{2}{\bigcup <!--\; \bigcup \; -->}}{A}_j\subseteq <!--\; \subseteq \; -->\underset{j=1}{\overset{2}{\bigcup <!--\; \bigcup \; -->}}{B}_j=A_1\bigcup <!--\; \bigcup \; -->A_2\subseteq <!--\; \subseteq \; -->B_1\bigcup <!--\; \bigcup \; -->B_2$. So P(2) holds.
Inductive step: Assume P(k) holds for some $k\ge <!--\; \ge \; -->2$. So $\underset{j=1}{\overset{k}{\bigcup <!--\; \bigcup \; -->}}{A}_j\subseteq <!--\; \subseteq \; -->\underset{j=1}{\overset{k}{\bigcup <!--\; \bigcup \; -->}}{B}_j=A_1\bigcup <!--\; \bigcup \; -->A_2\bigcup <!--\; \bigcup \; -->...\bigcup <!--\; \bigcup \; -->A_k\subseteq <!--\; \subseteq \; -->B_1\bigcup <!--\; \bigcup \; -->B_2\bigcup <!--\; \bigcup \; -->...\bigcup <!--\; \bigcup \; -->B_k.$
Notice, $\underset{j=1}{\overset{k+1}{\bigcup <!--\; \bigcup \; -->}}{A}_j\subseteq <!--\; \subseteq \; -->\underset{j=1}{\overset{k+1}{\bigcup <!--\; \bigcup \; -->}}{B}_j=A_1\bigcup <!--\; \bigcup \; -->A_2\bigcup <!--\; \bigcup \; -->...\bigcup <!--\; \bigcup \; -->A_k\bigcup <!--\; \bigcup \; -->A_{k+1}\subseteq <!--\; \subseteq \; -->B_1\bigcup <!--\; \bigcup \; -->B_2\bigcup <!--\; \bigcup \; -->...\bigcup <!--\; \bigcup \; -->B_k\bigcup <!--\; \bigcup \; -->B_{k+1}.$
So $P(k+1)$ olds and by induction P(n) holds for all $n\ge <!--\; \ge \; -->2$.

Group theory - Lagrange's theorem does not seem to hold
As per Lagrange's theorem, the order of a subgroup must perfectly divide the order of the group.
Let us take the group $G=(S,\mathrm{♯<!--\; ♯\; -->})$, where $S=\{1,3,5,7,9\}$ and $\mathrm{♯<!--\; ♯\; -->}$ suggests multiplication mod 10. G is a group, with being $O(G)=5$
Let us take a subset $H=\{1,3,7,9\}$, then $(H,\mathrm{♯<!--\; ♯\; -->})$ is also a group as it is closed, associative, satisfies identity and inverse laws. Thus H is a subgroup of S. $O(H)=4$. But I don't see Lagrange's theorem holding, as 4 does not divide 5.
Not sure if I'm making any silly mistake somewhere, would appreciate some help on this.

Equivalence classes when $x-<!--\; -\; -->y=$ multiple of 3?
𝑥 R 𝑦 exactly when $𝑥-<!--\; -\; -->𝑦$ equals a multiple of 3.
There exists equivalence classes [0], [1] and [2]. Prove that $[1]+[2]$ is equal to [0].
Not sure about the ambigious part, all I could find from my research was that if it's intepreted different ways the meaning will still be the same e.g. $[1]+[2]=[0]$ is the same as $[2]+[1]=[0]$ or $[0]=[2]+[1]$. But I am unsure about that.
How do I create these equivalence classes and prove that $[1]+[2]$ is equal to class [0] ?

How to convert a boolean function to CNF?
Consider the boolean function: $f(x,y,z)=(x+\stackrel{¯<!--\; ¯\; -->}{y})(y+\stackrel{¯<!--\; ¯\; -->}{z})(z+\stackrel{¯<!--\; ¯\; -->}{x})$
I have converted it to DNF which is $xyz+\stackrel{¯<!--\; ¯\; -->}{y}\stackrel{¯<!--\; ¯\; -->}{z}\stackrel{¯<!--\; ¯\; -->}{x}$, but I have problem with converting it to CNF.