The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

1
vote
1answer
49 views

Clarification on tribonacci numbers exercise

From what I know the Tribonacci sequence is given by: T(n) = T(n-1) + T(n-2) + T(n-3) My book says that "We can show by induction that for large enough n, the Fibonacci numbers satisfy the ...
3
votes
3answers
69 views

Use mathematical induction to show that $ H_{2^n} \geq 1+ \frac{n}{2} $

An Inequality for Harmonic Numbers. The harmonic numbers $H_j, j=1,2,3,...,$ are defined by $$H_j = 1 + \cfrac{1}{2}+\cfrac{1}{3}+...+\cfrac{1}{j}$$ Use mathematical induction to show that $$ H_{2^n} ...
0
votes
1answer
22 views

Difference between Inductive hypothesis and inductive goal

For example: $\forall x: \forall y: \forall z:$ x * (y + z) = (x * y) + (x * z) by induction on z, letting x and y be arbitrary. What would be my inductive hypothesis and inductive goal in this ...
0
votes
1answer
29 views

Prove that $(A\oplus B)\cap B^c = A - (A\cap B)$

I've a question: $(A\oplus B)\cap B^c = A - (A\cap B)$ First of all, I checked with Venn's diagram, and it seems to be true. But now I need to prove it with "if and only if" ways. I've tried ...
0
votes
2answers
294 views

How many 5-digit falling numbers are there?

A falling number is an integer whose decimal representation has the property that each digit except the units digit is larger than the one to its right. For example, $96520$ is a falling number ...
0
votes
1answer
34 views

Linear Algebra and Combinatorics

Let $F \subset 2^{[n]}$,where $[n] = \{1,...,n\}$. And $\forall A \in F :|A| = 1 \mod 2$. And $ \forall A,B \in F: A \neq B \to |A \cap B| = 0 \mod 2 $ Prove that $|F| \leq n$ I use linear algebra's ...
3
votes
2answers
79 views

Proving conditional probability property.

If if $A$ and $B$ are mutually disjoint (exclusive), then: $$\mathbb{P}(A|A\cup B)=\frac{\mathbb{P}(A)}{\mathbb{P}(A)+\mathbb{P}(B)}$$ So I suppose that $\mathbb{P}(A)$ has to occur after the event $...
2
votes
1answer
23 views

How to prove some conditional probability properties?

How to prove that(given that any conditioning event has probability $> 0$): 1.IF $\mathbb{P}(B)=1$, then $\mathbb{P}(A|B) = \mathbb{P}(A)$ for any $A$ Here, its obvious that $\mathbb{P}(A)$ is ...
1
vote
1answer
22 views

How to determine subsets of sigma-algebra?

Let $\mathcal{F}$ be a $\sigma$-algebra of subsets of $\Omega$ and suppose that $B \in \mathcal{F}$. Show that $\mathcal{G} = \{A \cap B : A \in \mathcal{F} \}$ is a $\sigma$-algebra of subsets of $B$...
1
vote
2answers
27 views

Proof by induction confused about inductive step

I have these notes, but I'm confused on what is happening at the inductive step. Theorem: $\forall n \in \mathbb{N} 3 | (n^3-n) $ Inductive Step: For $n \geq 0, show P(n) \Rightarrow P(n+1) is ...
0
votes
1answer
38 views

Let σ = 42153, write σ as a product of elementary transpositions.

Let $σ = 42153$ be a permutation of {$1, 2, . . . , 5$}. (a) Draw the bipartite graph corresponding to $σ$. (b) How many inversions does σ have? (c) Write σ as a product of elementary transpositions ...
1
vote
2answers
43 views

Prove using induction that $2^n < \binom{2n}{n} < 4^n$ for $n \geq 2$

Trying to prove that, for $n\geq2$, $2^n < \binom{2n}{n} < 4^n$. Inductive hypothesis: Assume $P(k)$ is true: \begin{align} 2^k < \binom{2k}{k} < 4^n \\\\ \end{align} Show $P(k+1)$ \...
0
votes
1answer
24 views

Modified Balls in Bins allowing “ Negative Number of Balls”

There is a well-known formula used to count the number of solutions to: $ x_1+x_2+...+x_k=n $ where $x_1,x_2,...,x_k $ are non-negative integers. I would like to know if there is a known formula to ...
1
vote
5answers
41 views

Solving non-homogeneous recurrence relations of type $a_{n+1} - a_{n} = c_{_1}n+c_{_2}$

I do not understand how to go about solving the following form of non-homogeneous recurrence relations; $a_{n+1} - a_{n} = c_{_1}n+c_{_2}$. I have the following question: $a_{n+1} - a_{n} = 2n+3$ ...
-1
votes
2answers
144 views

Combinations and permutations with falling numbers [closed]

A falling number is an integer whose decimal representation has the property that each digit except the units digit is larger than the one to its right. For example 96521 is a falling number but 89642 ...
1
vote
5answers
560 views

Flipping a fair coin 3 times. [closed]

if I flip a fair coin $3$ times, what is the probability that the coin comes up heads an odd number of times. any help please. I understand the probability(A=the coin comes up heads an odd number ...
1
vote
0answers
105 views

probability of getting an ace and a king.

1) we get a uniformly random hand of 2 cards from a standard deck of 52 cards. Determine the probability that this hand contains an ace and a king. 2) We get a uniformly random hand of 2 cards from ...
1
vote
1answer
47 views

A = {1, 2, 3, … , 10}. How many pairs of subsets of A like (X, Y) are there such that…

A = {1, 2, 3, ... , 10}. How many pairs of subsets of A like (X, Y) are there such that: (a) X = A and |Y| = 3? (b) $X \cap Y = \emptyset$ and $X \cup Y = A$? (c) $|X \cap Y| = 2$ ...
0
votes
1answer
37 views

Sterling Numbers of The Second Kind With Limitations Placed on Boxes/Parts

I know there are similar problems already on the board. However, none of the previously stated questions contain problems where limitations are placed on the BOXES. Thus, seeing that I am struggling ...
0
votes
0answers
13 views

Given m, k ∈ N; m is a perfect k th power if ∃n ∈ Z 3 m = n k . How can you recognize perfect k th powers from their prime decompositions?

Im in a discrete mathematics course, and I'm struggling with this question. Any help would be appreciated!! Given: m, k ∈ N; m is a perfect k th power if ∃n ∈ Z 3 m = n k How can you recognize ...
0
votes
2answers
67 views

Prove that gcd(m, n) | lcm(n, m) for any non-zero integers m, n

I was wondering if you could help me with this question, in discrete math. Prove that gcd(m, n) | lcm(n, m) for any non-zero integers m, n any help is appreciated!
0
votes
1answer
27 views

Creating a bijection to verify possible int sums

Alright, so I was asked to find the number of possible solutions to the inequality: $$x_1 + x_2 + x_3 \le 11$$ So, I was told to use an auxiliary variable to instead show: $$x_1 + x_2 + x_3 + x_4 = ...
2
votes
1answer
196 views

Chromatic number of complement of Petersen graph

Hello ladies and gentlemen. This is Petersen Graph - It is an undirected graph, it is $3$-regular and it's chromatic number is $3$. Proof: There is a circle with $5$ nodes (the outside pentagon), a ...
1
vote
2answers
42 views

Finding all the eigenvalues of the complete graph on $4$ vertices.

So on a complete graph of $4$ vertices we have $$ A= \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1& 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 &0 \end{bmatrix} $$ ...
1
vote
1answer
54 views

Planar bipartite graph

I know that the number of edges for a face in a bipartite is at least 4. Clearly, we cannot have 3, because we will need to move back to the other side to have face. But, I'm having difficulty in ...
1
vote
1answer
44 views

Division of a 3d hypercube using hyperplanes

We can define a four-dimensional $hypercube$ as the set of all vectors (w, x, y, z) where each variable is restricted to 0 ≤ w, x, y, x ≤ 1. A $hyperplane$ is the set of vectors (w, x, y, z) ...
0
votes
2answers
46 views

Prove that $\mathbb{|Q| = |Q\times Q|}$

I have this problem: Prove that $\mathbb{|Q| = |Q\times Q|}$ I know that $\mathbb Q$ is countably infinite. But then how can I prove that $\mathbb{|Q\times Q|}$ is countably infinite? Thanks ...
0
votes
0answers
43 views

What is a complete set? Why its useful?

I am learning Discreet Mathematics and while learning Boolean algebra I came across the term Complete Set, the prof says that any formula that can be written with ...
0
votes
2answers
52 views

Graph isomorphisms on 6 vertices with degree 3

I want to find another graph that has 6 vertices and each has degree $3$ that is not isomorphic to these two graphs below. I know that these two graphs are isomorphic. They will all have the same ...
0
votes
1answer
41 views

Proof for “A simple connected graph has n-1 edges iff it is a tree ” without induction.

I am trying to prove that a simple connected graph with n nodes has n-1 edges iff it is a tree. I could prove it using induction but I was wondering if there is any other method. As soon we add one ...
-5
votes
3answers
65 views

Is $(\Bbb Z, \cdot)$ a group? [closed]

Is $(\Bbb Z, \cdot)$ a group? Thank you!
0
votes
1answer
37 views

F - set of the subsets of set {1,…,n}. Prove |F| <= n if…

Let $\mathbb{K}_n = \{1,...,n\}$ and $\mathbb{F} \subset 2^{\mathbb{K}_n}$ 1) $ \forall{A} \in \mathbb{F_n}: |A| = 1 \mod 2 $ 2) $ \forall{A,B} \in \mathbb{F_n}: A \neq B \to |A \cap B| = 0 \mod 2 $...
1
vote
1answer
150 views

Average Game Length (Gambler's Ruin)

Two players, A and B, start a game with i and N-i chips, respectively. The game consists of repeatedly flipping a fair coin with A receiving 1 chip from B if heads turns up and B receiving 1 from A ...
0
votes
1answer
16 views

Extension of the set

Given the set: $$\{x | x \in \{a, b\}*~\text{AND}~|x| = 4~\text{AND}~\exists y \in \{a,b\}* : (x = aya)\}$$ Why does the answer look like this: $\{aaaa, aaba, abaa, abba\}$? What I don't understand ...
1
vote
2answers
43 views

What is the remainder of $31^{2008}$ divided by $36$?

What is the remainder of $31^{2008}$ divided by $36$? Using Euler's theorem, we have: $$ \begin{align*} \gcd(31,36) = 1 &\implies 31^{35} \equiv 1 \pmod{36} \\ &\implies 31^{2008} \equiv 31^{...
3
votes
1answer
58 views

Proof of $\lceil x \rceil + \lceil y \rceil \geq \lceil x + y \rceil$

I have been trying to prove $$ \lceil x \rceil + \lceil y \rceil \geq \lceil x + y \rceil $$ by using $$ x \leq \lceil x \rceil < x+1,\\ y \leq \lceil y \rceil < y+1,\\ x + y \leq \lceil x+...
0
votes
1answer
71 views

Combinations of 5 Member Commitees Selected From 8 people

2.1 Eight people, including Mary and Peter, are candidates to serve on a committee of five. (a) How many different committees are possible? (b) How many different committees are there that ...
-2
votes
1answer
23 views

In a Group, prove that there is a $g=k^2$ where $k∈G$. [closed]

Given $(G, ∗, I)$ a group where $g ∈ G$, it satisfies $g^n=I$ for some odd number $n$. How can I prove that there is a $g=k^2$ where $k∈G$.
0
votes
0answers
25 views

Computer Science/Discrete Math T/F Questions

I'm having difficulty with a few questions. I've put my answers in parenthesis. True or False The principle of inclusion-exclusion requires that the sets A and B should be disjoint in order to ...
-2
votes
1answer
59 views

Prove that the equation $x^2=x$ has the same solutions in rational numbers as in integers

I was wondering if you could help me start in my discrete math homework. I'm asked to prove that A = B: $A =\{x \in \mathbb{Z}\mid x^2 = x\}$ and $B = \{x \in \mathbb{Q}\mid x^2 = x\}$ I'm having ...
1
vote
1answer
32 views

Proof real number $\sqrt{3}$ is an irrational number [duplicate]

Given: Let $n$ be an integer. Then $n^2=3a$ for some integer $a$ if and only if $n=3b$ for some integer $b$. Proof real number $\sqrt{3}$ is an irrational number. Here is I have so far: Assume $\...
3
votes
1answer
68 views

Calculate $15^{843} \pmod{11}$

Calculate $15^{843} \pmod{11}$ My solution Fermat's little theorem Since $15 \equiv 4 \pmod{11}$ and according Fermat's Little Theorem $$4^{10} \equiv 1 \pmod{11}\;,$$ we shall have $$15^{843} \...
2
votes
1answer
67 views

Hamiltonian graph and connected components

Let $G = (V, E)$ be a Hamiltonian graph and $A \subseteq V$. Prove that the graph obtained from $G$ by removing all the vertices in $A$ has at most $|A|$ connected components. This seems a bit ...
0
votes
1answer
67 views

Hamiltonian graph and 2-connected graph

A non-complete graph is called 2-connected if it stays connected after removing a vertex (and all edges which are incident to that vertex). Show that a Hamiltonian graph is 2-connected. I'm having ...
15
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
2
votes
5answers
177 views

Show that $m(m^2 − 7)$ for any natural m is always divisible by 6

My question is: Show that $m(m^2 − 7)$ for any natural m is always divisible by 6 So i know we have to use fermat's little theorem which says that if $p$ is a prime number, then $n^p-n$ is divisible ...
0
votes
1answer
79 views

Equivalence Relations/Classes

Good day. Just a couple of questions on Equivalence Relations/Classes and proofs. Let X denote the number of ways to arrange 4 distinct elements (this was 24 as obtained via 4!) Consider the ...
0
votes
0answers
22 views

Commutative proof by induction

The distributive law for naturals is: $\forall x: \forall y: \forall z:$ x * (y + z) = (x * y) + (x * z) Suppose we set out to prove this by induction on z, letting x and y be arbitrary. What is our ...
2
votes
3answers
94 views

If $x^4 = 16$ then $x=2$ : Discrete Math [closed]

Can someone please explain to me, whether: if $x^4 = 16$ then $x=2$ is true or false and why? I don't get it :(
4
votes
0answers
48 views

Need a book recommendation for the Symmetric Group (Permutations)

I am looking for a textbook to read about permutations. Looking for something to cover such topics as: Representation of permutations (2-line arrays, cycles, bipartite graphs), inverses, involutions, ...