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

2
votes
3answers
38 views

Correct Form of a Logical Statement

I ran across a problem which has stumped me involving existential quantifiers. Let U, our universe, be the set of all people. Let S(x) be the predicate "x is a student" and I(x) be the predicate "x is ...
1
vote
1answer
45 views

Possible number of combinations from a subset

Let's say I have an set of elements like this: [0,1,2,3,4,5]. I want to figure out the max number of possible combinations using a max of 4 elements. Meaning using 2 or 3 is also a possibility: [0] ...
1
vote
2answers
36 views

Give recursive definition of sequence $a_n = 2^n, n=2,3, 4… where $ $a_1 = 2$

Give recursive definition of sequence $a_n = 2^n, n = 2, 3, 4... where $ $a_1 = 2$ I'm just not sure how to approach these problems. Then it asks to give a def for: $a_n = n^2-3n, n = 0, 1, 2...$ ...
2
votes
2answers
60 views

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ , I don't have an idea for solve the question. My attempt : $\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= ...
2
votes
5answers
53 views

Showing that $\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$ for all $n\geq 1$

Show that $$\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$$ for all $n\geq 1$ I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but ...
3
votes
1answer
97 views

Can we prove that set of irrational numbers is a set using Zermelo-Fraenkel axioms?

To remove paradoxes of naive set theory, We started with the axioms of Zermelo-Fraenkel and developed a set theory. Where we are building sets starting from a empty set. How to construct set of ...
1
vote
1answer
31 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
0answers
17 views

Clarification of conditional propositions [duplicate]

I am studying first order logic and we have been introduced to conditional propositions.$(p \Rightarrow q)\;$ The truth table for $p \Rightarrow q$ is this: ...
-4
votes
2answers
56 views

rearranging the digits of 7524693 [closed]

In the number 7524693, how many digits will be as far away from the beginning of the number if arranged in ascending order as they are in the number?
1
vote
1answer
55 views

Runs of white balls in sampling without replacement

There are $m$ white balls and $n$ black balls in a box. Balls are randomly drawn from the box with no return. Denote $X_1$ : number of white balls that been drawn before the first black. For $2 \leq i ...
2
votes
2answers
69 views

Order of statements in implication

The question is from Exercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let $M(x,y)$ be "$x$ has sent y an e-mail message", where the universe of discourse ...
1
vote
4answers
54 views

Discrete Maths Set Theory: Prove that $\left|(X^Y)^ Z\right|=\left|X ^{Y \times Z}\right|$.

I need to prove that $(X^Y)^ Z$ and $X ^{Y \times Z}$ are in bijective correspondence. Can anyone please help? EDIT: Chuks's version said: prove that $(X\times Y)\times Z\sim X\times(Y\times Z)$. ...
4
votes
3answers
65 views

Discrete math - Set theory - Symmetric difference: Proof for a given number.

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set ...
1
vote
5answers
61 views

Proving that that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$

How might I prove that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$? I am not sure the best place to start other than assuming $x\in(R \setminus S)\setminus T$ and trying to ...
0
votes
0answers
18 views

DFT of subdomain of periodic domain

$f(t_i,x_j)$ is a solution of stochastic differential equation on grid. $j=[0,N+1]$, $i=[0,\infty]$ and boundary conditions are periodic: $f(t_i,x_0) = f(t_i,x_N)$ and $f(t_i,x_{N+1}) = f(t_i,x_1)$ ...
0
votes
0answers
28 views

Asymptotical stability of a discrete dynamical system

There is a linear time invariant discrete system, \begin{align} x_{k+1}&=\tilde{A}x_k, \end{align} where $\tilde{A}$ is a block matrix represented by \begin{align} \tilde{A}= ...
-1
votes
1answer
69 views

What is the inverse function of gcd? [closed]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
0
votes
1answer
83 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
0
votes
0answers
21 views

Repertoire method in solving recurrence [duplicate]

I don't know, how should I start solving this: $$a_1 = 2 \\ a_n = 2a_{n-1} +7$$ using the repertoire method. Could anyone give me an algorithm or explain, how to use this method in this case?
0
votes
3answers
31 views

Proving $a=b \bmod 19$ is an equivalence relation

My question is: $a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation) Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and ...
0
votes
1answer
26 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
3
votes
4answers
124 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
2
votes
3answers
76 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
3
votes
2answers
47 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of ...
0
votes
1answer
38 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
0
votes
0answers
33 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
1answer
51 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
0
votes
1answer
45 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
0
votes
1answer
14 views

About cycles and the values in the range of a permutation function

Let $f = \{(x_1 y_1), (x_2 y_2), \ldots, (x_n y_n)\}$ be a permutation. A cycle of $f$ is given by $g = (1, f(1), f^2(1), f^3(1) \ldots)$. When counting permutations, we usually drop $1$ and count ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
0answers
18 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this ...
0
votes
0answers
17 views

Integer problem to minimize cuttings

A company has to make 4 items in the given quantities. item1 =4 item 2=2 item3=1 item 4=1 Te surfaces has to be covered in plywood.The company has got 3 ...
0
votes
0answers
33 views

Let $(12)$ and $(23)$ be cycles. Then is $(12)(23)$ a permutation?

The reason I ask this is because sometimes we talk about non-disjoint cycles, for example: $(ab)(bc) \neq (bc)(ab)$. Do we consider $(ab)(bc)$ a permutation where $f(b) = a$ and $f(b) = c$?
-4
votes
1answer
58 views

Prove that there doesn't exist any integer $x \ge 3$ such that $x^2-1$ is prime. [closed]

Prove that there doesn't exist integer $x \ge 3$ such that $x^2-1$ is prime.
1
vote
1answer
26 views

Countability of the set of weighted graphs

Could you help me find the solution for this problem that consists in finding out wether the set of all weighted and finite graph is countable of not? As a reminder, a weighter graph can be seen as a ...
1
vote
1answer
24 views

Graphically representing relations of ordered pairs

I am having problems trying to picture what this relation of ordered pairs 'looks' like: Let R be the relation on the set of ordered pairs of positive integers such that ((a, b),(c, d)) ∈ R if and ...
1
vote
1answer
19 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
0
votes
3answers
47 views

Proving ${\sum}^n _{i=1}i = \frac {n(n+1)}{2}$ by induction

I am having problems understanding how to 'prove' a summation formula. I have the equation: $ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $ Basis Step when: $ n=1 $ $ {\sum}^1 _{i=1}i = \frac ...
2
votes
1answer
33 views

Property of maximum matching

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex v such that every incident edge is part of a maximum matching. I'm not sure how to prove this. How can every edge that ...
0
votes
1answer
25 views

Projection of a discrete subgroup of $R^n$ [duplicate]

Let $A$ be a discrete subgroup of $\Bbb R^n$ and let $V$ be a $m<n$ dimensional $\Bbb R$-subspace of $\Bbb R^n$. Is the projection of $A$ onto $V$ a discrete subgroup? I am most interested in the ...
2
votes
2answers
32 views

Shortcut for composing cycles

Let $\pi = (15)(14)(13)(12).$ To compose the cycles of $\pi$, I rewrite $(15)(14)(13)(12)$ as $[(15)(2)(3)(4)][(14)(2)(3)(5)][(13)(2)(4)(5)][(12)(3)(4)(5)]$ which is tedious. Is there any way to ...
0
votes
2answers
18 views

Verifying the reasoning is true for the following deductive arguent

Identify the premises and conclusions of the following deductive arguments and analyze their logical forms. Do you think the reasoning is valid? Either John or Bill is telling the truth. Either Sam ...
2
votes
1answer
32 views

Smallest integer

I encountered an intriguing problem and I think I have a solution, but I want to run it by some of the smarter people around here: Find the smallest integer $n, n>1$ such that $C(n)=n, C(n)$ is ...
0
votes
1answer
31 views

Finding a twin prime in binary expansion

Numbers from 1 to 63 are placed on 6 cards according to the following 6 rules: The 1st digit in the binary expansion of each number on card 1 is a one. The 2nd digit in the binary expansion of each ...
0
votes
1answer
51 views

3 men and a cold night [duplicate]

$3$ guys, each with $\$10$ a piece, go to a hotel hoping to get a room to stay in for the night. A room costs $\$60$. The men go in, and ask to rent a room, only having $\$30$ between them. The mater ...
2
votes
0answers
51 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
1
vote
1answer
32 views

General methods of solving non-linear recurrences

Let's consider a sequence $$ \{a_{n} \} _{n=0}^{\infty}, a_{0}=1, a_{n+1}=\frac{a_{n}}{1+na_{n}}$$. Taking $$b_{n}=\frac{1}{a_{n}},$$ we bring the exact reccurence to the following one: $$b_{0}=1, ...
-2
votes
4answers
89 views

For each natural number $n$, let $A_n = \{nx \mid x\in \Bbb Z\}$. What is $\bigcap^∞_{i=1} A_i$? [closed]

The universe of discourse is the set of all integers. Let $A_n = \{nx \mid x\in \Bbb Z\}$ for each natural number $n$. What is $\bigcap^∞_{i=1} A_i$?
-2
votes
1answer
70 views

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? [closed]

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? Having a hard time proving this statement.
0
votes
2answers
56 views

Induction question regarding Universe

I was given a question that looks like this. Prove that for each $2 \le n\in \mathbb N$, if $X_1,\ldots,X_n$ are subsets of some universe $U$, then the following is true: $$(X_1 \cup\cdots\cup ...