Explore Discrete Math Examples

Intro to Discrete Math: compound interest calculation
Scroll to the part with the bolded algebraic equations.
I understand the formula:
$S=A(1+R)+A(1+R{)}^2+...+A(1+R{)}^n$
As well known, this S can be put into a more compact form by first computing $S-<!--\; -\; -->(1+R)S$ as $S=A((1+R{)}^{n+1}-<!--\; -\; -->(1+R))/R$
I have no idea what $S-<!--\; -\; -->(1+R)S$ or where it's gotten from.

Solving the recurrence $a_{k+2}=\frac{k-<!--\; -\; -->4}{(k+1)(k+2)}{a}_k$?
I am solving the ODE $y^{″}-<!--\; -\; -->x{y}^{\prime }+4y=0$ via power series, which leads me to the following recurrence:
$$\begin{array}{}\text{(1)}& a_{k+2}=\frac{k-<!--\; -\; -->4}{(k+1)(k+2)}{a}_k\end{array}$$
where $k\ge <!--\; \ge \; -->1$ and $a_0,a_1$ are given. I would like to ask a question about one of the steps in my solution (in red below), and whether there is a better solution.

Questions about Predicate Logic in relation to a Word Problem?
I am struggling to undersand Predicate Logic and my teacher gave me an interesting problem that is just a little confusing. I am unsure what I need to exactly describe these situations. I gave it a go but I would appreciate any insights into what I might be doing wrong.
You are writing a program that keeps track of movies and actors. The situation can be described using the following predicates:
R(M,Y) is true if movie M was released in year Y.
S(A,M) is true if actor A appears in movie M.
H(M) is true if the movie M was a hit!
Use these predicates to state the following facts:
(a) Actor “A” has appeared in at least one hit.
(b) Actor “A” has appeared in at least two hits.
(c) Actors “A1” and “A2” have appeared together in the same movie.
(d) All the movies that Actor “A” appears in are hits.
(e) Actor “A” appears in all the hits released in ”2020”.
My solutions so far:
a. $(\mathrm{\exists <!--\; \exists \; -->}x)S(A,M)\to <!--\; \to \; -->H(M)$
b. $(\mathrm{\exists <!--\; \exists \; -->}x)S(A,M)\to <!--\; \to \; -->H(M)\wedge H(M)$
c. $(\mathrm{\exists <!--\; \exists \; -->}x)S(A_1,M)\wedge S(A_1,M)$
d. $(\mathrm{\forall <!--\; \forall \; -->}x)S(A,M)\to <!--\; \to \; -->H(M)$
e. $(\mathrm{\forall <!--\; \forall \; -->}x)S(A,M)\to <!--\; \to \; -->H(M)$ in 2020

Chinese Remainder Theorem, discrete math problem
$5^{2003}$ $\equiv <!--\; \equiv \; -->$ 3(\mathrm{mod}7)$$
$5^{2003}$ $\equiv <!--\; \equiv \; -->$ $4(\mathrm{mod}11)$
$5^{2003}\equiv <!--\; \equiv \; -->8(\mathrm{mod}13)$
Solve for $5^{2003}$ (mod 1001) (Using Chinese remainder theorem).

Discrete Math - Sets and Complements
I have the following problem: List the elements of the set $\stackrel{¯<!--\; ¯\; -->}{A\cap <!--\; \cap \; -->B}\cup <!--\; \cup \; -->C$, where $\stackrel{¯<!--\; ¯\; -->}{X}$ denotes the complement of an arbitrary set X and U denotes the universe under consideration. The considered sets are as follows:
- $U=\{1,2,3,\dots <!--\; \dots \; -->,10\}$
- $A=\{1,4,7,10\}$
- $B=\{1,2,3,4,5\}$
- $C=\{2,4,6,8\}$
I believe I have the answer but not too sure. Here's what I came up with:
$$\stackrel{¯<!--\; ¯\; -->}{A\cap <!--\; \cap \; -->B}\cup <!--\; \cup \; -->C=\{2,3,5,6,7,8,10\}.$$
Is this answer correct and more so written correctly?

Uniqueness Proof for Discrete Math
Can someone show me how to prove the uniqueness of (p is prime and q is prime and $p-<!--\; -\; -->q=3$)?

Is $x^2=y^2$ a symmetric relation?
$R=\{(x,y):x^2=y^2\}$ and I have to determine whether its an equivalence relation.
I found that it's reflexive but for the symmetry part I got confused as $x=y$ is sometimes said to be symmetric others not so I don't know what to take it as.

Show that $G_{n,p}$ does not contain a certain subgraph.
LEMMA. Let $a=a(n),c=c(n)$ be functions of n such that $a(n)\ge <!--\; \ge \; -->1.1$ and $c(n)=$ $o\left(a{n}^{1-<!--\; -\; -->1/a}\right).$. Then, for $p(n)=c(n)/n,G(n,p)$ a.s. contains no subgraphs with s vertices, $s\le <!--\; \le \; -->0.35{\left(\frac{2a}{c}\right)}^{a/(a-<!--\; -\; -->1)}\exp <!--\; \; -->(-<!--\; -\; -->\frac{2}{a-<!--\; -\; -->1})n$, and more than as edges.

Combinations of 5 letters and 3 numbers in an 8 digit password
I'm having a pretty hard time solving this relatively simple problem. Essentially, the problem asks how many 8 digit passwords can be formed using 5 different letters from a set of uppercase and lowercase letters (thus, 52 letters in total) and 3 different digits from the set of integers $0-<!--\; -\; -->9$. My solution so far is that there are $(\genfrac{}{}{0ex}{}{8}{5})(\genfrac{}{}{0ex}{}{52}{5})(\genfrac{}{}{0ex}{}{10}{3})$ possible passwords, but I have no way of checking is this is true and the other problems haven't come quite so easily to me. Am I correct? If not, how can I find the correct answer?

A coin is flipped six times. In how many possible outcomes are the number of heads and tails not equal?
This is an example question from my Discrete Mathematics course textbook. I'd like help on whether I'm approaching it correctly and how to continue from where I am, that is if I'm right so far.
A coin is flipped six times where each flip comes up either heads or tails. In how many possible outcomes are the number of heads and tails not equal?
I've figured out that order doesn't matter, indicating I'll use combination and that there are 64 possible outcomes $(2^6=64)$ and that for the number of heads and tails not to be equal any outcome is possible apart from 3 heads and 3 tails. I'm fairly new to this so I'm not sure how to proceed from here.

Proving $\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n}{2k})\frac{1}{2k+1}=\frac{2^n}{n+1}$ using the extraction/absorbtion identity.
I want to use the extraction/absorbtion identity to prove the equality
$$\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n}{2k})\frac{1}{2k+1}=\frac{2^n}{n+1}$$
Followed from this identity, we could directly obtain
$$(\genfrac{}{}{0ex}{}{n+1}{2k+1})=\frac{n+1}{2k+1}(\genfrac{}{}{0ex}{}{n}{2k})$$
Then we have
$$\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n}{2k})\frac{1}{2k+1}=\frac{1}{n+1}\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n+1}{2k+1})$$
Then how can I prove that $\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n+1}{2k+1})=2^n$?

Can I show that $n\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n})=0$?
A brief question: I know that $(\genfrac{}{}{0ex}{}{n}{k})$ isn't defined for $n<k$, however, can I show that $n\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n})=0$? if so how can I do that? I saw through wolfram that it really is zero, and I was wondering how he got into it. I have encountered this debate in a question when I needed to find a closed form of the next series:
$$\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})(n-<!--\; -\; -->k)$$
And instead of getting n out first, I have tried to do the following steps:
$$\begin{gathered} \underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})(n-<!--\; -\; -->k)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{n!}{k!(n-<!--\; -\; -->k)!}(n-<!--\; -\; -->k)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{n!}{k!(n-<!--\; -\; -->k-<!--\; -\; -->1)!} \\ =n\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{(n-<!--\; -\; -->1)!}{k!(n-<!--\; -\; -->k-<!--\; -\; -->1)!}=n\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})=n[(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n})+\underset{\begin{array}{l}\text{by Newton's binomial}\\ \text{it is }{2}^{n-<!--\; -\; -->1}\end{array}}{\underset{⏟<!--\; ⏟\; -->}{\underset{k=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})}}] \\ =n[(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n})+2^{n-<!--\; -\; -->1}]=n(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n})+n{2}^{n-<!--\; -\; -->1} \end{gathered}$$
Now is it valid to right this as final result of a closed form for $\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})(n-<!--\; -\; -->k)$?

Given sets A and B, the symmetric difference $A\mathrm{△<!--\; △\; -->}B$ is defined by $A\mathrm{△<!--\; △\; -->}B=(A-<!--\; -\; -->B)\cup <!--\; \cup \; -->(B-<!--\; -\; -->A)=(A\cup <!--\; \cup \; -->B)-<!--\; -\; -->(A\cap <!--\; \cap \; -->B)$.
let $X=\{1,2,3,...271\}$
a) $\mathrm{\forall <!--\; \forall \; -->}A\in <!--\; \in \; -->P(X),\mathrm{\exists <!--\; \exists \; -->}B\in <!--\; \in \; -->P(X),271\in <!--\; \in \; -->A\mathrm{△<!--\; △\; -->}B$. Prove it true or false.
So this is my understanding is as follows with what I think my mistake might be in brackets.
"$\mathrm{\forall <!--\; \forall \; -->}A\in <!--\; \in \; -->P(X)$" For any possible A set, it will be a member of the power set of X.
( So I view A as all possible P(X), otherwise it would be written "$A\in <!--\; \in \; -->P(X)$" right ? )
"$\mathrm{\exists <!--\; \exists \; -->}B\in <!--\; \in \; -->P(X)$" There is a B set, that is a member of the power set of X.
( I view B as a single possible set from P(X). )
"$271\in <!--\; \in \; -->A\mathrm{△<!--\; △\; -->}B$" 271 is a member of the symmetric difference between A and B.
( So, "when all possible sets of P(x) are compared to a specific set of P(X), the result would be "$271\in <!--\; \in \; -->A\mathrm{△<!--\; △\; -->}B$" every time." is the statement? )

How many perfect matches are there in a graph with n connected components?
Let $G=(V,E)$ be a graph with n connected components, in which each component $G_i$ is the $K_{2i}$ graph. How many perfect matches are there in G?

How many 5-digit numbers are there, so that 0,1 and 2 are NOT included, 3,4 and 5 have to be included
I have the following question. How many 5-digit numbers are there, so that the following conditions are satisfied:
- 0,1 and 2 are NOT included
- 3,4 and 5 have to be included
The list of possible numbers to choose from is (3,4,5,6,7,8,9). As we know, 3,4 and 5 have to be included in every number, for example 33475, 54339 etc.
I tried to do this as follows:
For the 1. digit, I can choose 3,4 or 5. So, I basically have $(\genfrac{}{}{0ex}{}{3}{1})$ choices. For the 2. digit, I have 2 numbers to choose from, for example 4 or 5 if 3 is the 1. digit, 3 or 5 if 4 is the 1. digit etc. So, that's $(\genfrac{}{}{0ex}{}{2}{1})$. For the 3. digit there is 1 number to choose as per reasoning for choosing the 2. number. That's basically $(\genfrac{}{}{0ex}{}{1}{1})$. For the 4. and 5. digit, there are $(\genfrac{}{}{0ex}{}{7}{1})$ possibilities respectively, because any number from the list can be chosen.
At the end I get $(\genfrac{}{}{0ex}{}{3}{1})\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{2}{1})\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{1}{1})\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{7}{1})\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{7}{1})=3\cdot <!--\; \cdot \; -->2\cdot <!--\; \cdot \; -->1\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->7=294$ possible numbers. Now, you can permute those choices between the digit places. There are 5 digits, so it would be $5!=120$ possible permutations. In the end I got $294\cdot <!--\; \cdot \; -->120=35280$ numbers. However, the problem is that there are not 120 such permutations, because for some cases one number is counted multiple times.
I know from my class that the answer is 1830. And I also got the hint from my professor to use the inclusion-exclusion principle. But with that I have problems to start.
So, could somebody help me either how to calculate this with the inclusion-exclusion principle OR with the way I tried to do this, i.e. how to NOT multiple count those numbers.

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the bottom drawer will have at least 1 ball?
problem 2: from a group of 5 women and 6 men you need to choose a council made of a ceo, vp, cto, cfo. in how many ways can you do that such that the ceo is a women and the oldest of the men will be in the council?
problem 3: given a triangle on the plane; on each of its edges are 5 points that are not on the vertices. how many triangles can be created when each of their vertices are on the points stated?

A multigraph G has even no of Hamiltonian paths
Definition (Stick) : A path $s=e_1,...,e_m$ in G,where the end vertices of the edge $e_i$ are $v_i$ and $v_{i+1}$ and $1\le <!--\; \le \; -->i\le <!--\; \le \; -->m$. The path s is called a stick.
Corollary : Let G be a multigraph, let $u,v\in <!--\; \in \; -->V$, and suppose that d(w) is odd for each vertex $w\in <!--\; \in \; -->$ V- {u,v} $\ne <!--\; \ne \; -->\mathrm{\varphi <!--\; \varphi \; -->}$. Then number of Hamiltonian Paths in G from u to v is even.
Proof: We may assume that u and v are adjacent vertices (if they are not we may add an edge between them); let e be an edge between u and v. We choose the stick s to be the edge e with $u=u_1$ and $v=v_2$; if $w\in <!--\; \in \; -->V$ then $\mathrm{ϵ<!--\; ϵ\; -->}(w)$ is the number of edges from u to w.Consequently a Hamiltonian path h beginning with s and ending in w gives rise to exactly $\mathrm{ϵ<!--\; ϵ\; -->}(w)$ hamiltonian paths from u to v. But by Theorem 1.1 the number of such paths ending in the set $W=\{w\in <!--\; \in \; -->V:\mathrm{ϵ<!--\; ϵ\; -->}(w)$ is odd} is even.
My understanding of proof :
- Since the graph is Hamiltonian if the edge uv is missing we add it.
- Now that stick s has to be the edge with $u=v_1$ does this mean $u=v_1$ is incident with last edge of stick.
- For Hamiltonian paths to be to be even it is obvious that after deletion of {u,v} we are left with vertices of odd degree and since its a multigraph loops are allowed which leads to set W being have paths of odd length i.e $\mathrm{ϵ<!--\; ϵ\; -->}(w)$ is odd so we have even number of vertices and sum of odd degrees with even no of vertices is even.
But what I dont get from the proof is how there are ϵ(w) Hamiltonian paths?

"Compute $\underset{j=0}{\overset{m}{\sum <!--\; \sum \; -->}}{3}^j(\genfrac{}{}{0ex}{}{m}{j})$
The result should be somewhat familiar. Then, use the binomial theorem to verify the result."
I'm having some serious trouble with this problem. I'm not sure how to start computing.
What is the first step here?

How to write formal proofs?
Prove that a 0-2 finite binary tree satisfies the condition: $n_e=n_i+1$
Proof 2: Induction on height of btree, call it h

Does triangulation have to be finite for Sperner's Lemma to Apply?
I'm a little confused about a proof I read for Sperner's Lemma. The context was described as follows: Assume we have a n-dimensional simplex that is partitioned into smaller simplices that are either disjoint or share a full face. Sperner's Lemma states that a proper coloring of such a simplical subdivision must contain a simplex whose vertices share no colors in common, and in particular, there must be an odd number of such simplices (mod n).
However, I'm a little confused by the proofs I've seen for the 1-dimension and 2-dimension cases. If we have the simplex as a line segment, it doesn't seem obvious to me that if we have a non-finite number of vertices in the interior of the segment that there need be an odd number of line segments that have differently colored endpoints; couldn't there be an infinite number of such segments? Similarly, the proof I saw for the 2d case seems to use the handshake lemma, which only applies to finite graphs.