Explore Discrete Math Examples

Geometry and Strong inductions Discrete Math
Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs . Show, by strong induction, that no matter how you split the piles, the sum of the products computed at each step equals $n(n-<!--\; -\; -->1)/2$
I dont get this because say n is 20 and i split it to 10 and 10. I multiply those two numbers together and i get 100. When i do 20(20-10)/2, i dont get 100. What am i doing wrong?

Show the $\frac{1}{a}+\frac{3}{b}>1$ for this planar graph.
The connected planar graph, G satisfies the (1) ~ (3).
(1) The number of the vertex of the G is n.
(2) The degree of all the vertices are 4.
(3) Each vertex of G lies on exactly one face of degree a and exactly three faces of degree b (Here the d(f) is a degree of the face and $a<b$)
Show the $\frac{1}{a}+\frac{3}{b}>1$
In the solution it claimed like the below.
First, $\frac{1}{a}+\frac{3}{b}>1$
The number of the faces whose degree is the a ; $\frac{n}{a}$ (*)
The number of the faces whose degree is the b ; $\frac{3n}{b}$ (**)
Hence, $v-<!--\; -\; -->e+f=n-<!--\; -\; -->2n+(\frac{n}{a}+\frac{3n}{b})=2$. From this it deducted the results $\frac{1}{a}+\frac{3}{b}>1$.
But My question is why are the (*) and (**) hold? Is there any particular reason for claiming those?

Could you help me to start this demonstration by contrapositive
If a,b,c are positive numbers such that $a+b>c$, then $a>c/2$ or $b>c/2$.

The following combinatorial equality is true? If yes, anyone can give me a hint how to prove it?
$$\underset{n=x}{\overset{M}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{x})q^x(1-<!--\; -\; -->q{)}^{n-<!--\; -\; -->x}(\genfrac{}{}{0ex}{}{M}{n})r^n(1-<!--\; -\; -->r{)}^{M-<!--\; -\; -->n}=(\genfrac{}{}{0ex}{}{M}{x})q^x{r}^x(1-<!--\; -\; -->qr{)}^{M-<!--\; -\; -->x}$$
where $0<r,q<1$

If Alice gives Bob m candies, then he'll have n times her candies; if Bob gives Alice n candies, then she'll have m times his candies.
Alice and Bob have some different amount of candies (>1 each). If Alice gives Bob m candies, then Bob has n times the candies remaining to Alice, and if Bob gives Alice n candies, then Alice has m times the candies remaining to Bob.
How many candies have Alice and Bob?
I expected infinite solutions, but running a simple Python code (up to 200 iterations) gave me only 4 answers:
$$\begin{array}{cccc}\text{A}& \text{B}& m& n\\ 7& 5& 3& 2\\ 14& 4& 8& 2\\ 11& 5& 7& 3\\ 11& 7& 8& 5\end{array}$$
Apparently the highest amount of candies that Alice/Bob can have is 14.
Does this limit actually exist? If so, how can I prove that?

For any real number x and positive integer k, define the notation [x,k] by the recursion $[x,k+1]=(x-<!--\; -\; -->k)[x,k]$ and $[x,1]=x$.
If n is any positive integer, one can now express the monomial $x^n$ as a polynomial in $[x,1],[x,2],...,[x,n]$. Find a general formula that accomplishes this, and prove that your formula is correct.

Permutation of rings in Discrete Math
If we have 4 different beads, how many braclets can we make if it can't be flipped and rotations resulting in similar results?
- 4!/4
If we are allowed to flip?
- 4!/4/2
Consider the size of all bracelets with distinct beads where the size of the bracelet is the number of beads. What is the counting sequence?
I do not know what it means by counting sequence, can someone explain to me what it wants?

How many ways to construct an increasing list given $N^2$ cards
There are N people and $N^2$ cards. They are divided into N cards with the number 1, N with the number 2, N with the number 3, and so on. Each person will choose one card and give it back afterwards. How many ways to make a line with N cards such that they are sorted in increasing order For example: 4 will give 35 ways. (1,2,3,4, 2,2,2,4 , 3,4,4,4, ...etc)
The answer I found is $(\genfrac{}{}{0ex}{}{N+N-<!--\; -\; -->1}{N})\to <!--\; \to \; -->(\genfrac{}{}{0ex}{}{2N-<!--\; -\; -->1}{N})$. However, I cannot see the logic behind it?

Discrete Math Letters (Combination or Permutation)?
Given the letters a,b,c. How many ways to arrange these letters?
Assuming 3 letters.
Logical Question:
How do you know if you need to use permutations or combinations for this question ?
P(3,3) or C(3,3) ?

Find all positive integers a and b such that $7^a-<!--\; -\; -->3(2^b)=1$
I am looking for all positive integers satisfying the equation
$$7^a-<!--\; -\; -->3(2^b)=1$$
I used the fact that (1,1) is a solution and got
$$(7^a-<!--\; -\; -->7)=3(2^b-<!--\; -\; -->2)$$
I thaught about using Gauss Theorem in vain. Thanks in advance for any idea.

2-Coloring a tree with 2n vertices with additional constraint
Suppose given a tree $\mathcal{T}$ with n pair of vertices $\mathcal{T}$. But my problem is as follow:
I want coloring $\mathcal{T}$ with 2 colors such that each pair $(p_i,q_i)$ has different color. Are there any proof or paper that show us it's possible or not?

Discrete Math on Isomorphic Graphs
I'm not sure how to show or draw that no self-complementary graphs can exist or not for the following question.
Show that no self-complementary graphs with 6 or 7 vertices can exist.

Why is $(\genfrac{}{}{0ex}{}{n}{k})$ for fixed n not Gosper summable?
I am trying to understand the book $A=B$ which has many much more complicated expressions which are Gosper-summable but then on p. 102 he states $(\genfrac{}{}{0ex}{}{n}{k})$ for fixed n as a function of k is not Gosper-summable. How can this be? Can someone show why it is not Gosper-summable?

Discrete mathematics - ternary strings.
Let n be a natural number, n≥3. A ternary string is a sequence of n symbols that has some of the digits 0, 1, 2. In other words, a ternary string is a n-permutation with a repetion of the set $\{\mathrm{\infty <!--\; \infty \; -->}\cdot <!--\; \cdot \; -->0,\mathrm{\infty <!--\; \infty \; -->}\cdot <!--\; \cdot \; -->1,\mathrm{\infty <!--\; \infty \; -->}\cdot <!--\; \cdot \; -->2\}$. I wonder how to find the number of ternary strings that have at least one 0, one 1 and one 2.
I know that there is a inclusion-exclusion principle, and for that we need to know at least the number of items in the sets, such as A, B and so on.. That being said simply adding the elements in A and B together will show us the elements in the intersection, however we will need to substract the intersection of A and B in order to obtain the number of elements in the union. My confusion is if there is something different by being a ternary string and also by the domain of the sets that has those ternary strings, the mathematical approach I'm thinking of is something like:
$$A\cup <!--\; \cup \; -->B=A+B-<!--\; -\; -->A\cap <!--\; \cap \; -->B$$

Discrete Math: Proof by Induction
I need to prove $3^{4n+2}+5^{2n+1}$ is divisible by 14 for $n=0,1,2\dots <!--\; \dots \; -->$I did the base case $n=0$ and everything checked out. Then I assumed $n=k$ and want to prove $k+1$.
$3^{4k+6}+5^{2k+3}=$
That's how far I got, what would I do next? Separate powers?

Discrete math equation: True or False
There exists an n for all m such that $m\cdot <!--\; \cdot \; -->n=n$ .
I am confused on how to approach this problem.
Thanks in advance!
edit: Is this true or false?
I originally thought false due to the fact that there is only one m such that the equation is valid.

1. Assume a and b are irrational numbers. Find a counterexample showing that it is possible $a-<!--\; -\; -->b$ is rational.
2. If $x+1$ is odd, prove that $(x+1{)}^3$ is odd.

Prove that $2^5+3^4$ cannot be expressed as $\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{3}^i{2}^{z_i}$ for a given n, where $z_i$ is in descending order
This landed on my lap as a work proof, but I can't seem to wrap my mind around it.
You have $Z=\{z_0,z_1,...,z_n\}$ where zi are non-negative integers in descending order.
I need to show that $2^5+3^4$ cannot be expressed as $\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{3}^i{2}^{z_i}$, for some Z and n. It is easy to see that the expression can never be 0(mod3), but I can't find a proof for $2^5+3^4$.

This is my work so far:
- D(n) is the number of ways the set {1,2,3,…,n} can be partitioned into two sets.- $D(n-<!--\; -\; -->1)$ is the number of ways the set $\{1,2,3,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1\}$ can be partitioned into two sets.
$n-<!--\; -\; -->1$ can be divided into two sets, say, A and B. Now we add element n into A and B.
Now each partition of $D(n-<!--\; -\; -->1)$ gives two partitions of D(n):
- $D(n)=2D(n-<!--\; -\; -->1)$
To solve:
let $D(n)=r^n$
$r^n=2r^{n-<!--\; -\; -->1}$
$r=2$
$D(n)=2Rn$
Is my logic correct?

Combinatorial justification on $n^2=(n-<!--\; -\; -->1{)}^2+2(n-<!--\; -\; -->1)+1$
Not sure how how to prove this through combinatorial justification, now I know that the RHS is just $n^2$ after simplification but that would be an algebraic proof not combinatorial.
In the LHS, say there are a group of size of 2n items, evenly separated into 2 sub-groups, each sub-group contain exactly n items. To pick 2 items total, that is to pick 1 item from each of the sub-groups, together there will be $n^2$ of possibility to pick from.
Now the RHS. I can say that $(n-<!--\; -\; -->1{)}^2$ is somewhat similar from what i described above but with only a sub-group that has size $(n-<!--\; -\; -->1)$, in the end, you would still be able to pick 2 items that each is from a $(n-<!--\; -\; -->1)$ sub-group.
And that $2(n-<!--\; -\; -->1)=2n-<!--\; -\; -->2$. Which is kind of similar like $n-<!--\; -\; -->1$ situation but is choosing from $2n-<!--\; -\; -->2$ size group of items. in the end, you just add another item with +1 at the end to combine into 2 items ..